백준 1253번 좋다 (C++)

문제 링크 : https://www.acmicpc.net/problem/1253

1253번: 좋다

문제 요약

 

1. n개의 숫자가 주어집니다.

2. n개의 숫자 내에서, i번째 숫자가 서로 다른 두 숫자를 합쳐 나타낼 수 있다면 해당 i번째 숫자는 좋은 수 입니다.

3. 좋은 수의 갯수를 출력하세요.

 

핵심 포인트

 

문제에서 설명이 다소 불친절한 경향이 있습니다.

i번째 숫자를 서로 다른 두 숫자의 합으로 나타낼 때, i번째 숫자는 포함시켜선 안됩니다.

ex : 0 0 0
정답 0

ex : 0 3 3
정답 : 2

이분 탐색을 이용해 문제를 풀 수 있습니다.

 

문제 풀이

 

코드 자체가 간결한 편이므로, 전체코드에서 핵심만 설명하도록 하겠습니다.

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, ans = 0;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin >> v[i];
    sort(v.begin(),v.end()); // 1
    for(int i=0; i<n; i++){ // 2
        int l=0, r=n-1; // 3
        while(l<r){ // 4
            if(l==i){l++; continue;} // 5
            if(r==i){r--;continue;}
            if(v[i]>v[l]+v[r]) l++; // 6
            else if(v[i]==v[l]+v[r]){ // 7
                ans++;
                break;
            }
            else r--; // 8
        }
    }
    cout << ans << "\n"; // 9
    return 0;
}

(1) 벡터에 n개의 숫자를 입력받고 오름차순으로 정렬해줍니다.

(2) n개의 숫자만큼 for문을 돌립니다. n개는 최대 2000개이므로, 이를 이분탐색과 결합해도 시간초과가 발생하지 않습니다.

(3) l = 0, r = n-1에서 시작합니다.

(4) l < r 의 조건일때까지만 while문을 돌립니다.

(5) 만약 l==i이거나 r==i일 경우, 서로 다른 두 숫자의 합으로 나타낼 때, i번째 숫자는 포함시켜선 안된다는 규칙을 지키지 못합니다.

l==i일 경우 l++을 하고, r==i일 경우 r--를 합니다.

(6) 만약 v[i] > v[l]+v[r]일 경우, l++을합니다.

(7) v[i] == v[l]+v[r]일 경우 정답을 찾았으니 ans를 +1하고 break합니다.

(8) v[i] < v[l] + v[r]일 경우, r--을 합니다.

(9) 정답을 출력합니다.