(C++) - 백준(BOJ) 1253번 : 좋다

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

1253번: 좋다

이분탐색으로 푼 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. n, ans, 일차원 배열 num을 선언 후 n만큼 수를 입력받습니다. 2. num을 오름차순으로 정렬해줍니다.

 

📔 풀이과정

오름차순으로 정렬되어 있으니 i번째 수를 두 수의 합으로 나타내려면 그 두 수의 위치는 무조건 0 ~ i-1 사이에 존재합니다. num[i+1]부터는 하나의 수 만으로도 num[i]를 넘기 때문에 두 개의 수에 대한 합으로 표현할 수 없기 때문입니다. 하지만 반례가 존재하는데 0이 포함된 경우입니다. 이 경우에 어떤 두 0의 합으로 0을 만들 수 있으며 0 + 3 = 3처럼 서로 다른 위치의 두 수를 더해도 같은 수가 나올 수 있습니다. 따라서 경우를 나누어 다음과 같이 판별합니다.

 

 1. 모든 수가 0인 경우 : n을 출력하고 프로그램을 종료합니다.

 

 2. 그 이외의 경우 : i번째 수가 좋은지 판별하기 위해 i와는 다른 j를 기준으로 num[i] - num[j]이상인 곳의 위치를 이분탐색으로 찾습니다. 해당 값은 idx라는 변수에 저장합니다. idx또한 j또는 i와 같을 수 있으므로 이 경우에는 답으로 간주하지 않습니다. i, j와 같지 않으며 num[idx] + num[j] == num[i]인 경우 ans를 하나 더해주며 break해줍니다. 이렇게 O(N^2logN)의 시간복잡도로 해결할 수 있습니다.

 

📔 정답출력

ans를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, ans, num[2001];

bool isAllZero(){
    for(int i = 0; i < n; i++)
        if(num[i]) return false;
    return true;
}

int main(){
    cin >> n;

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

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

    sort(num, num + n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == j) continue;
            auto idx = lower_bound(num , num + n, num[i] - num[j]) - num;
            if(idx == i || idx == j) continue;
            if(num[idx] + num[j] == num[i]) {
                ans++; break;
            }
        }
    }
    
    cout << ans;
}