1253번 (gold 4)

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

투포인터를 사용한 문제이다. 문제의 난이도는 알고리즘의 난이도라기 보다는 데이터 갯수에 의한 알고리즘 판단과 예외처리 때문에 난이도가 골드인 것 같다.

 

#include <iostream> 
#include <vector>
#include <algorithm>

using namespace std;
int main() {
	int N;
	cin >> N;
	long arr[2000] = {};
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
	}

	sort(arr, arr + N);
	int count = 0;

	for (int i = 0; i < N; ++i) {
		int start = 0, end = N - 1;
		while (end > start) {
			if (arr[i] == arr[end] + arr[start]) {
				if (start != i && end != i) {
					count++;
					break;
				}
				else if (start == i) {
					start++;
				}
				else
					end--;
				//cout << "arr[" << i << "]: " << arr[i] << " " << end << " " << start << "\n";
			}
			else if (arr[i] > arr[end] + arr[start]) start++;
			else end--;

		}

	}
	cout << count;
	return 0;
}

서로 다른 수의 합이 N이 되면 좋은 수라고 판단하는데 서로 다른 수 중에 자기 자신이 포함되면 안된다는 예외를 처리해야한다.

0 + n = n 상황은 이 문제에서 원치않는 답으로 보임.