BOJ 1253 : 좋다

• 문제 링크 : boj.kr/1253
• 난이도 : G4
• 태그 : 정렬, 이분탐색

1253번: 좋다

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    vector<ll> arr(n);
    for(auto &u : arr) cin >> u;
    sort(all(arr));

    int ans = 0;
    for(int i = 0; i < n; i++) {
        i = i;
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            bool check = false;
            int target = arr[i] - arr[j];
            if(min(i,j) > 0) check |= binary_search(&arr[0], &arr[min(i,j)], target);
            if(max(i,j)-1 >= min(i,j)+1) check |= binary_search(&arr[min(i,j)+1], &arr[max(i,j)], target);
            if(max(i,j) < n-1) check |= binary_search(&arr[max(i,j)+1], &arr[n], target);
            if(check) {
                ans++;
                break;
            }
        }
    }
    cout << ans;
    return 0;
}

---

풀이

어떤 수 X가 좋은 수인지 판단하기 위해 합을 이루는 두 수 A, B를 찾아보자.

A, B를 찾는 방법은 정말 많겠지만 그 중 하나를 고정하고 나머지를 찾는 방식으로 해결할 수도 있다.

 

우선 A를 고정한 채로 B가 가능한 수가 있는지 찾아보자.

X와 A가 고정되었기 때문에 B또한 정해진다. 따라서 B가 주어진 수열에 존재하는지 확인하면 된다.

수열을 미리 정렬해둔다면 이분탐색으로 확인할 수 있다. 단, B의 후보에 X와 A가 들어가지 않도록 유의해야 한다.

나의 경우 X와 A가 포함되지 않도록 구간을 나누어 해결했다.

 

위처럼 풀 경우 X별로 확인하는 데에 O(N), 후보 A를 선택하는 데에 O(N), B를 찾는 데에 O(logN)으로 총 O(N^2logN)으로 해결할 수 있다.