백준 1253 좋다 [C++] 풀이 및 코드

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

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

	
	int n;
	cin >> n;

	vector<int> arr(n, 0);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;

		arr[i] = a;
	}
	//A번
	sort(arr.begin(), arr.end());

	//B번
	int good = 0;
	if (n < 3)
	{
		cout << "0";
		return 0;
	}

	for (int i = 0; i < n; i++)
	{
		int obj = arr[i];
		int start = 0;
		int end = n-1;
		//C번
		if (i == 0)
		{
			start++;
		}
		else if (i == n - 1)
		{
			end--;
		}
		//D번
		while (start < end)
		{
			if (start == i)
			{
				start++;
			}
			else if (end == i && start != end - 1)
			{
				end--;
			}

			if (arr[start] + arr[end] > obj)
			{
				end--;
			}
			else if (arr[start] + arr[end] < obj)
			{
				start++;
			}
			else
			{
				if(start != i && end != i) good++;
				break;
			}

		}

		
	}

	cout << good;
	
	return 0;
}

 

풀이

일단 랜덤한 수가 들어온 경우를 생각 해 보자.

 

 

다음과 같을 때, start와 end(two-pointer)를 옮겨야 하는 기준을 잡아야 한다.

A번 설명

물론 하나하나 더해가며 답을 찾으면 되지만, 이러면 시간이 너무 많이잡아 먹으니 더 단순하게 생각해 보자.

필자는 two-pointer가 움직이는 기준을 기존 방식인 합의 크기로 하였다.

 

합의 크기가 작거나 클 경우 two-poiner를 옮겨줘야 하는데, 이는 들어온 입력이 랜덤한 경우 어려워진다.

이유는 two-pointer의 기초를 생각하면 되는데, 정렬된 숫자인 경우 합의 크기가 크면 end를 우측으로 옮겨 점점 합의 크기를 키우면 된다.

하지만 랜덤한 경우 우측으로 옮겼다고 해서 합이 커진다는게 보장되지 않는다.

따라서 정렬하는 코드가 필요하다.

B번 설명

문제를 보면, 입력한 수 중 하나를 다른 2개와 더한 값으로 나올 때 good인 경우다.

따라서 입력된 수 N(1 ≤ N ≤ 2,000), 의 범위를 고려했을 때 3이하이면 0으로 출력되며 프로그램이 끝나는 코드를 작성했다.

C번 설명

시작은 다음과 같다.

이 때 만약 N개의 수 중에서 어떤 수가 0번 즉 start와 동일하면 안되기 때문에 start를 ++해줌으로써 다음과 같이 변경 해 주는 코드를 작성하자.

(예를들어 1(index=0)이 나올 수 있는 2개의 수를 고를 때, 자신을 포함하면 안되기 때문이다)

이와 동일하게 end도 자신을 포함할 수 있기에 --를 해주는 것이다.

 

D번 설명

정렬된 숫자에서 특정 합을 구하기 위해 two-pointer의 기본을 사용한다.

이때 예외가 나오게 되는데, 합이 작아 start를 계속 옮기게 되면 어느 순간 찾고자 하는 index까지 가게 된다. 

이때도 자신을 포함하면 안되기 때문에, ++를 하면 된다.

 

하지만 ++를 함으로써 end와 겹치는 상황이 올 수 있다.

문제에 나와있듯 다른 두개의 즉 n1+n2인거지 n1+n1인 상황이 오면 안되기 때문에 이를 방지해 주는 코드를 작성해 주어야 한다.

그게 start와 end가 각각 i가 아닌 경우의 코드를 의미한다.

 

start가 합 목표 index까지 가게되는 것과 동일하게 end도 그럴 수 있다.

동일한 의미로 --를 한번 더 하게 되는데, 이 때에도 start와 end가 겹칠 수 있다.

따라서 start가 end-1이 아닐 때 조건을 작성해야 한다.