[백준 1253번] 좋다

[백준 1253번] 좋다

www.acmicpc.net/problem/1253

1253번: 좋다

 

 

 문제

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

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

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

 

 

 입력

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

 

 

 출력

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

 

 

 풀이

#include <iostream>
#include <algorithm>
using namespace std;
int arr[2000];
int main() {
	int N; cin >> N;
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	sort(arr, arr+N);
	int cnt = 0;
	for(int i=0;i<N;i++){
		int lp = 0;
		int rp = N-1;
		if(lp == i) lp++;
		if(rp == i) rp--;
		int target = arr[i];
		while(lp < rp){
			int k = arr[lp] + arr[rp];
			if(k > target) rp--;
			else if(k < target) lp++;
			else{ cnt++; break;}
			
			if(lp == i) lp++;
			if(rp == i) rp--;
		}
	}cout << cnt;
	return 0;
}

 정렬하고 모든 값에 대해 투포인터 돌려보면 되는 문제이다. 포인터가 가르키는 대상이 자기일 때만 제외해주면 된다. 좋은 수의 개수를 찾는 것이지 좋은 수가 되게 하는 방법의 가짓수를 요구하는 것이 아니기 때문에 찾는 즉시 break 해준다. 이게 왜 골드4일까?