문제

나의 요약

어떤 수가 주어진 수들 중 다른 두 개의 합으로 나타낼 수 있으면 좋은 수이다.
주어진 수들 중 좋은 수는 몇 개인지 출력하라.

접근 방식

배열을 정렬해, 한 숫자에 대해서 투 포인터 방식으로 제일 좌측과 우측에서 시작해서 더해보면 어떨까 싶었다. 그 더한 결과가 찾으려는 숫자보다 크면 우측을 좌측으로 한칸 옮기고, 작으면 좌측을 우측으로 한칸 옮기는 식이다. 좌측과 우측이 만날 때까지 숫자를 찾지 못하면 그 숫자는 좋은 수가 아닌 것이다.

이것을 모든 수에 대해서 반복해도 수의 개수는 최대 2000개이기 때문에, 적어도 N*N의 수보단 적게 반복할 것이다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> nums;

void Input()
{
	cin >> N;
	nums.assign(N, 0);
	for(int i = 0; i < N; i++)
	{
		cin >> nums[i];
	}
	sort(nums.begin(), nums.end());
}

void Solve()
{
	int numOfGood = 0;
	for(int i = 0; i < N; i++)
	{
		int left = 0, right = N-1;
		while(left < right)
		{
			if(left == i)
			{
				left++; continue;
			}
			if(right == i)
			{
				right--; continue;
			}
			
			int sum = nums[left] + nums[right];
			if(sum == nums[i])
			{
				numOfGood++;
				break;
			}
			else if(sum > nums[i])
			{
				right--;
			}
			else
			{
				left++;
			}
		}
	}
	
	cout << numOfGood;
}

int main()
{
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cout.tie(NULL);
  	
  	Input();
  	Solve();
}

Solve 함수를 보면 위의 접근 방식대로다. 추가된 것이 있다면 찾으려는 수의 인덱스는 건너뛰는 것이다. 같은 수는 영향을 줄 수 있어도, 인덱스까지 같은 수는 영향을 끼치지 못하기 때문이다. 이것을 배열의 모든 수에 대해 반복하면 알맞은 답이 나온다.

회고

원래는 접근방식을 위처럼 생각했다가, 중간에 '어 그냥 브루트포스로 전부 수 더해봐서 있는지 찾아버리면 되지 않나?' 라고 생각이 들어서 잠깐 바꿨었다. 하지만 더한 수에서 '같은 인덱스'가 영향을 끼쳤는지를 제대로 파악하지 못해서 틀린 결과가 나왔다. 이 부분을 해결해보려 했지만, 브루트포스로는 빠른 결과로 만들지 못할 것 같아서 다시 바꿨다.
이번에는 꽤 빠르게 풀이법을 바꿔 좋은 결과를 이끌어냈다. 틀리면 접근을 바꾸는 것에 주저치 말자.