[C++] 백준 1253번: 좋다

문제 링크

1253번: 좋다

문제 요약

N개의 수 중에 한 수를 자기 자신을 제외한 두 수의 합으로 나타낼 수 있으면 '좋다'고 한다. N개의 수가 주어지면 좋은 수가 몇 개인지 구해야 한다.

접근 방법

일단 저는 unordered_set을 이용해서 풀었는데 잘 푼거 같지는 않습니다. C++로 푸신 다른 분들은 100ms 근처에서 AC를 받으셨는데, 제 경우에는 첫 AC에서 1950ms를 받았고, 수정한 풀이는 800ms를 받았습니다.

기본적인 접근 방법은, 모든 조합의 두 수의 합을 구해서 set에다가 집어 넣는 것입니다. 하지만 두 수 중 하나 또는 둘 모두 0인 경우에는 예외로 처리를 해줍니다.

두 수 모두 0인 경우에는 두 수를 포함해서 0이 3개 이상 있어야 좋은 수가 될 수 있습니다. 두 수 중 하나가 0인 경우에는, 다른 수가 2개 이상 있어야 합이 좋은 수가 될 수 있습니다. 입력을 받을 때, map에 수의 갯수를 저장해서 갯수를 알아야 하는 부분만 별도로 처리해 주었습니다.

그 외에는 모든 합을 set에 담은 뒤에, N개의 수들을 각각 set에 들어있는지 확인시켜 주었습니다.

코드

#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>

using namespace std;

vector<int> v;
unordered_set<int> s;
unordered_map<int, int> m;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	v.resize(n);
	int zero = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
		if (v[i] == 0)
			zero++;
		m[v[i]]++;
	}

	if (zero >= 3)
		s.insert(0);

	for (int i = 0; i < v.size(); i++)
	{
		for (int j = i + 1; j < v.size(); j++)
		{
			if (s.find(v[i] + v[j]) != s.end())
				continue;
			if (v[i] == 0 && v[j] == 0)
				continue;
			if (v[i] == 0 && m[v[j]] == 1)
				continue;
			if (v[j] == 0 && m[v[i]] == 1)
				continue;
			s.insert(v[i] + v[j]);
		}
	}

	int ans = 0;
	for (auto& i : v)
		if (s.find(i) != s.end())
			ans++;

	cout << ans;
	return 0;
}