백준 1253번 좋다 (C++)

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp (int a, int b){
    return a<b;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;
    vector <int> num(N,0);
    
    for (int i=0;i<N;i++){
        cin >> num[i];
    }
    
    sort(num.begin(), num.end());

    int cnt = 0;
    
    for (int num_idx=0;num_idx<N;num_idx++){
        long find = num[num_idx];
        int start_idx=0, end_idx=N-1;
        
        while (start_idx<end_idx){
            if (num[start_idx]+num[end_idx]==find){
                if (start_idx!=num_idx && end_idx!=num_idx){
                    cnt++;
                    break;
                }
                else if (start_idx==num_idx){
                    start_idx++;
                }else if (end_idx==num_idx){
                    end_idx--;
                }
            }
            else if ((num[start_idx]+num[end_idx])>find){
                end_idx--;
            }
            else {
                start_idx++;
            }
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

 

간단해 보이는데 사실 반례 때문에 까다로운 문제다. 

3
0 0 0
정답: 3

3
0 0 1
정답: 0

 

상식적으로 생각하면

int start_idx=0, end_idx=N-1;

가 아닌 

int start_idx=0, end_idx=num_idx-1;

가 맞다.

 

                else if (start_idx==num_idx){
                    start_idx++;
                }else if (end_idx==num_idx){
                    end_idx--;
                }

 

도 사실 num_idx를 넘어가서까지 search를 하겠다는 말이기 때문에 뭔가 이상하다.

 

하지만 이래야 반례가 해결된다.