백준 7453 - 합이 0인 네 정수 (C++)
4개의 배열이 주어지고, 동일한 개수의 숫자가 각 배열에 할당된다.
이 때, 각 배열에서 1개씩 선택하여 나온 4개의 숫자를 더한 값이 0이되는 경우의 수를 구하면 된다.
문제 풀이
처음엔 메모리나 시간초과를 생각하며, 이 방법이 진짜 맞나? 이런 생각이 들었지만 결론적으로는 그냥 생각나는대로 풀면 된다.
먼저, A,B,C,D 이렇게 주어진 4개의 배열을 (AB) (CD)이렇게 2개로 줄여주었다.
A와 B의 원소를 합해서 나올 수 있는 모든 경우의 수를 하나의 배열에 저장해주었고, C와 D도 동일하게 합해서 나올 수 있는 모든 경우의 수를 하나의 배열에 저장해주었다.
이렇게 합치고 나면, 두개의 배열만 남게 되는데 두 배열에서 각 원소를 합했을 때 0이되는 경우의 수를 구해주면 된다.
4개의 배열에서 합했을 때 0이되는 경우의 수는 구하기 매우 까다롭고 경우가 많지만, 2개의 배열이라면 정렬해준 뒤에 투 포인터나 이분탐색으로 쉽게 답을 구할 수 있다. 본인은 이분탐색을 활용하였다.
엄밀히 말하면 이분탐색을 사용하는 std함수인 std::lower_bound와 std::upper_bound를 사용하였다.
std::lower_bound : 배열에서 특정 값보다 크거나 같은 원소가 처음으로 나온 위치를 반환해준다.
ex) {1, 2, 3, 4, 5} 에서 3을 lower_bound에 대입한다면, 3이 처음으로 나온 3번째 원소를 가리키는 이터레이터를 반환해준다.
std::upper_bound : 배열에서 특정 값을 초과하는 원소가 처음으로 나온 위치를 반환해준다.
ex) {1, 2, 2, 4, 5} 에서 2를 upper_bound에 대입한다면, 2보다 큰 값이 처음으로 나온 4번째 원소를 가리키는 이터레이터를 반환해준다.
lower_bound와 upper_bound를 사용한 이유는 배열 내에 동일한 값이 여러개 있을 경우를 고려하였기 때문이다.
예를 들어, AB와 CD의 원소가 각각 (-3, -4) (4, 4) 라고 한다면, 두 원소를 합해서 0이되는 경우는 2가지이다.
이 때, AB의 원소 -4를 기준으로 했을 때, CD에 존재하는 4의 개수가 -4와 합해서 0이되는 경우의 수가 될 것이다.
그러므로, (upper_bound를 통해 나온 인덱스 - lower_bound를 통해 나온 인덱스)의 값이 해당 원소와 합했을 때 0이되는 원소의 개수라고 판단할 수 있다.
AB를 기준으로, 원소를 하나씩 순회하면서 AB의 원소와 절대값은 같지만 부호가 다른 값이 CD내부에 몇개씩 있는지 탐색하면서 나온 값을 ZeroCount라는 변수에 저장해주었고 최종적으로 ZeroCount를 출력하여주었다.
풀이 코드
int SizeOfSequence = 0;
std::cin >> SizeOfSequence;
std::vector<int> A(SizeOfSequence);
std::vector<int> B(SizeOfSequence);
std::vector<int> C(SizeOfSequence);
std::vector<int> D(SizeOfSequence);
for (int i = 0; i < SizeOfSequence; i++)
{
std::cin >> A[i] >> B[i] >> C[i] >> D[i];
}
먼저, 모든 입력을 받아 각 배열에 저장해주었다.
std::vector<int> AB(SizeOfSequence * SizeOfSequence);
std::vector<int> CD(SizeOfSequence * SizeOfSequence);
for (int i = 0; i < SizeOfSequence; i++)
{
for (int j = 0; j < SizeOfSequence; j++)
{
AB[j + SizeOfSequence * i] = A[i] + B[j];
CD[j + SizeOfSequence * i] = C[i] + D[j];
}
}
이후, A와 B를 AB라는 하나의 배열에 합쳤고, C와 D를 CD라는 하나의 배열에 합쳐주었다.
AB의 원소는 A의 원소와 B의 원소를 더했을 때 나올 수 있는 모든 경우의 값이다.
CD의 원소는 C의 원소와 D의 원소를 더했을 때 나올 수 있는 모든 경우의 값이다.
std::sort(AB.begin(), AB.end());
std::sort(CD.begin(), CD.end());다음으로 두 배열을 정렬해주었다. 이분탐색을 활용할 때엔 정렬이 필수적이다.
(upperbound와 lowerbound는 이분탐색을 활용하기 때문에 정렬해주어야 한다.)
int MaxIndex = SizeOfSequence * SizeOfSequence - 1;
long long ZeroCount = 0;
for (int i = 0; i <= MaxIndex; i++)
{
int CurValue = AB[i];
int LowerBound = std::lower_bound(CD.begin(), CD.end(), -CurValue) - CD.begin();
int UpperBound = std::upper_bound(CD.begin(), CD.end(), -CurValue) - CD.begin();
ZeroCount += UpperBound - LowerBound;
}
std::cout << ZeroCount;
return 0;
다음으로, 반복문을 돌면서 위에서 설명했던 것과 같이 UpperBound와 LowerBound를 활용하여 원소의 개수를 탐색하고 있다.
만약, lower_bound에서 특정 값을 찾지 못한다면 어떻게 될까?
lower_bound는 주어진 값과 동일한 원소를 찾는 것이 아니라, 주어진 값보다 크거나 같은 값을 탐색한다. 그러므로 원하는 값을 찾지 못했다면, 그 값보다 큰 값중에서 가장 앞에 있는 원소의 위치를 반환할 것이다.
upper_bound는 주어진 값을 초과하는 원소를 찾는 함수이기 때문에, 만약 원하는 값이 배열에 없다면, lower_bound와 upper_bound는 같은 값을 반환할 것이다. 그러므로 UpperBound - LowerBound는 0이 된다.
이렇게 ZeroCount에 값을 계속 더해준 뒤, 반복문이 끝나고 출력해주면 끝이다.
코드 전문
#include <iostream>
#include <vector>
#include <algorithm>
void Init()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
int main()
{
Init();
int SizeOfSequence = 0;
std::cin >> SizeOfSequence;
std::vector<int> A(SizeOfSequence);
std::vector<int> B(SizeOfSequence);
std::vector<int> C(SizeOfSequence);
std::vector<int> D(SizeOfSequence);
for (int i = 0; i < SizeOfSequence; i++)
{
std::cin >> A[i] >> B[i] >> C[i] >> D[i];
}
std::vector<int> AB(SizeOfSequence * SizeOfSequence);
std::vector<int> CD(SizeOfSequence * SizeOfSequence);
for (int i = 0; i < SizeOfSequence; i++)
{
for (int j = 0; j < SizeOfSequence; j++)
{
AB[j + SizeOfSequence * i] = A[i] + B[j];
CD[j + SizeOfSequence * i] = C[i] + D[j];
}
}
std::sort(AB.begin(), AB.end());
std::sort(CD.begin(), CD.end());
int MaxIndex = SizeOfSequence * SizeOfSequence - 1;
long long ZeroCount = 0;
for (int i = 0; i <= MaxIndex; i++)
{
int CurValue = AB[i];
int LowerBound = std::lower_bound(CD.begin(), CD.end(), -CurValue) - CD.begin();
int UpperBound = std::upper_bound(CD.begin(), CD.end(), -CurValue) - CD.begin();
ZeroCount += UpperBound - LowerBound;
}
std::cout << ZeroCount;
return 0;
}