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

 

 

문제 1253번

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

 

 

이번 문제는 투포인터를 사용하는 문제이다. N개의 수 중 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있는지 알아내고, 그 개수를 출력하면 된다.

 

배열에 수를 넣고 해당 수의 개수만큼 정렬을 해준다(투포인터를 이용하려면 정렬은 필수!). 투 포인터 left에는 0, right에는 N-1로 초기화한다. 같은 수의 합으로 나타내면 안 되기 때문에 left가 right보다 작을 때까지 계속해서 반복해주고, left,right를 인덱스로 넣은 값의 합과 찾을 숫자를 비교해준다.

 

같다면 서로 다른 숫자의 합이 찾는 값이어야하기 때문에 찾을 숫자의 인덱스 i와 left, right를 비교해준다. 둘 다 같지 않다면 좋은 수의 개수를 늘려준 후 반복문을 빠져나오고, i와 같다면 각 left나 right의 값을 이동시켜준다. 

 

찾아야하는 값보다 합이 더 크면 숫자를 줄여줘야하기 때문에 right--를 해주고, 작으면 숫자를 키워야하기 때문에 left++해준다.

 

그렇게 나온 result값이 좋은 수의 개수이므로 출력해주면 된다.

 

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

int N, result = 0;
int num[2000];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	sort(num, num + N);

	for (int i = 0; i < N; i++) {
		int left = 0, right = N - 1;
		int target = num[i];	// 찾을 숫자
		while (left < right) {
			if (num[left] + num[right] == target) {
				if (left != i && right != i) {	// 서로 다른 숫자의 합이어야하기 때문에
					result++;
					break;
				}
				else if (left == i) {
					left++;
				}
				else if (right == i) {
					right--;
				}
			}
			else if (num[left] + num[right] > target) {
				right--;
			}
			else {
				left++;
			}
		}
	}
	cout << result;

	return 0;
}