[백준/C++] 1253 좋다

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

1253번: 좋다

# 문제 설명

- N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다"라고 한다.

- N개의 수가 주어질 때, 그 중에서 좋은 수의 개수는 몇 개인지 출력한다. 수의 위치가 다르면 값이 같아도 다른 수이다.

 

# 풀이 방법

- 오름차순 정렬 후 각각의 수가 좋은 수인지 찾는다.

- 투포인터 (s=0, e=n-1)를 통해 두 인덱스 값의 합이 목표보다 작으면 e--, 크면 s++를 해준다.

- 인덱스가 목표 인덱스와 겹치지 않도록 주의한다.

 

# 정답 코드

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

int n;
long long arr[2010];
int ans = 0;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);

	if (n < 3) {
		cout << 0;
		return 0;
	}

	for (int i = 0; i < n; i++) {
		int s = 0;
		int e = n-1;
		while (s<e) {
			if (arr[s] + arr[e] < arr[i]) {
				s++;
			}
			else if (arr[s] + arr[e] > arr[i]) {
				e--;
			}
			else {
				if (s == i) s++;
				else if (e == i) e--;
				else {
					ans++;
					break;
				}
			}
		}
	}

	cout << ans;
}