C++) 백준 1253 좋다

1253번: 좋다

---

코드

 

#include <algorithm>
#include <iostream>

using namespace std;

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

	long long x[2005] = { 0 };
	int n, cnt = 0;

	cin >> n;
	for (int i = 0; i < n; i++) cin >> x[i];

	sort(x, x + n);

	if (n < 3) { cout << cnt; return 0; }
	if (!x[0] && !x[2]) cnt++;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			int low = lower_bound(x, x + n, x[i] - x[j]) - x;

			if (low == j || low == i)continue;
			if (x[low] + x[j] == x[i]) {
				cnt++; break;
			}
		}
	}
	cout << cnt;
}

 

 

풀이

 

a + b = c 일 경우 c - b = a 임을 이용

 

c : 코드 상의 x[i]

b : 코드 상의 x[j]

a : 코드 상의 x[i] - x[j]

 

1. 이분 탐색을 이용하여 배열 내 값 a의 하한에 해당하는 인덱스를 찾아 변수 low에 삽입

2. low 인덱스 값의 중복 여부 판단 후 a + b = c의 성립 여부 확인

3. 성립 시 카운팅 후 중복 방지를 위해 반복문 탈출