백준 - 1253번 좋다 (C++)

Pixabay로부터 입수된 Niek Verlaan님의 이미지 입니다.

 

---

 

https://www.acmicpc.net/problem/1253

1253번: 좋다

 

 이번 문제는 N개의 숫자들이 주어질 때, 특정 숫자가 다른 두 개의 숫자의 합과 같은 경우가 몇 가지인지를 구하는 문제이다. 이 문제의 알고리즘 분류에는 이분 탐색, 두 포인터(투 포인터)가 있다. 하지만 이번에는 저 두 알고리즘을 이용하지 않고 모든 경우를 다 구했다.

 

 우선, 특정 숫자가 다른 두 개의 숫자의 합과 같은지를 알기 위해서는 서로 다른 위치의 숫자 두 개를 합해야 할 것이다. 그렇기에 가능한 모든 경우의 합을 아래처럼 구했다.

vector<int> nums;	// nums: 입력으로 주어진 숫자들
map<int, vector<pair<int, int>>> sumCheck;	// 특정 숫자를 구할 수 있는 두 수의 위치들

for (int frontIdx = 0; frontIdx < N; ++frontIdx)
{
	for (int backIdx = frontIdx + 1; backIdx < N; ++backIdx)
	{
		int sum = nums[frontIdx] + nums[backIdx];
		
		// frontIdx번과 backIdx번 숫자를 더할 경우, sum이라는 숫자를 만들 수 있다
		sumCheck[sum].push_back({ frontIdx, backIdx });	
	}
}

여기서 단순히 sum(두 숫자의 합)이 존재하는지만 체크해도 될 것 같지만, 그렇지 않다. 예를 들어, 입력이 이렇게 들어온다고 하자.

 

입력

3 

0 0 1

 

출력

0

 

 

이 경우, 첫 번째 숫자와 세 번째 숫자를 더해서 1을 만들 수 있다. 그리고 첫 번째 숫자와 두 번째 숫자를 더해서 0을 만들 수 있다. 그렇기에 단순히 합의 존재만 저장한다면 0보다 큰 값이 출력될 것이다. 하지만 0, 1은 좋은 수가 아니다. 즉, 답은 0이어야 한다.  왜냐하면 세 번째 숫자인 1이 좋은 수가 되려면 자기 자신(세 번째)과는 다른 숫자 두 개를 합해서 1이 되어야 하기 때문이다. 0도 마찬가지로 좋은 수가 아니다. 그렇기에 단순히 합이 되는 숫자가 존재하는지만 판별해서는 안된다. 대신 두 숫자의 위치들을 저장하였다.

 

 모든 합의 경우를 찾은 후, 입력된 숫자들이 생성될 수 있는지를 판별해야 한다. 이는 아래처럼 구하였다.

int count = 0;

for (int idx = 0; idx < nums.size(); ++idx)
{
	int num = nums[idx];

	for (int k = 0; k < sumCheck[num].size(); ++k)
	{
		if (sumCheck[num][k].first != idx && sumCheck[num][k].second != idx)
		{
			++count;
			break;
		}
	}
}

모든 숫자들을 검사한다. 그리고 sumCheck에 자기 자신을 만들 수 있는 위치들을 저장한 배열을 검사한다. 만약 어떤 두 위치가 모두 자기 자신의 위치가 아니라면, 다른 두 수의 합이 자기 자신과 같다는 뜻이기에 count를 1 증가시킨 후 탐색을 끝낸다. 이러한 과정을 거쳐, 입력받은 모든 숫자들이 자기 자신 외 다른 두 수의 합으로 나타내질 수 있는지 확인할 수 있다. 아래는 모든 과정이 담긴 코드이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#pragma warning(disable:4996)
using namespace std;

int N;
vector<int> nums;
map<int, vector<pair<int, int>>> sumCheck;

int Check()
{
	int count = 0;

	for (int frontIdx = 0; frontIdx < N; ++frontIdx)
	{
		for (int backIdx = frontIdx + 1; backIdx < N; ++backIdx)
		{
			int sum = nums[frontIdx] + nums[backIdx];

			sumCheck[sum].push_back({ frontIdx, backIdx });
		}
	}

	for (int idx = 0; idx < nums.size(); ++idx)
	{
		int num = nums[idx];

		for (int k = 0; k < sumCheck[num].size(); ++k)
		{
			if (sumCheck[num][k].first != idx && sumCheck[num][k].second != idx)
			{
				++count;
				break;
			}
		}
	}

	return count;
}

int main()
{
 	ios_base::sync_with_stdio(0);
	std::cout.tie(0);
	std::cin.tie(0);

	cin >> N;

	for (int n = 0; n < N; ++n)
	{
		int num;
		cin >> num;

		nums.push_back(num);
	}

	sort(nums.begin(), nums.end());

	int answer = Check();

	cout << answer << endl;

	return 0;
}

 

 여담으로, 여기서 main에서 sort를 이용하여 입력한 숫자들을 오름차순으로 정렬하였다. 왜냐하면 두 수의 합을 구하는 문제이기에 값이 작은 숫자들은 합의 대상이 잘 되지 않을 것이라 생각했다. 그래서 미리 정렬을 통해 작은 숫자들을 쉽게 넘길 수 있게 하려 했다. 실제로도 sort(nums.begin(), nums.end()); 부분을 지우고 제출을 하니 아래처럼 시간 초과가 발생했다.

 

---

참고 예제

https://www.acmicpc.net/board/view/100953