[BOJ / C++] 1253번 : 좋다

문제

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

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

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

입력

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

출력

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

Solved.ac 레벨

골드 IV

풀이

아직 어떤 문제를 딱 접했을 때 문제 유형이 뭔지 파악하는 능력이 부족한 것 같다.

아무튼 이 문제는 투 포인터 문제였다.

 

어떤 정수가 두 정수의 합이 될 수 있는지를 판단할 때 작은 수 + 큰 수의 조합을 확인해보기 위해 수열을 오름차순으로 정렬시킨 뒤 0부터 n n - 1번째 수를 각각 탐색했다.

 

예제

n = 10

1, 2, 3, 4, 5, 6, 7, 8, 9, 10 을 통해 풀이 과정을 설명하겠다.

수열은 int형 vector v를 이용해 저장했다. 예제에서 주어질 때부터 정렬이 되어있다.

작은 수 + 큰 수의 조합을 확인하겠다고 하였으므로 start = 0, end = n - 1 = 10 - 1 = 9에서부터 탐색을 한다.

 

v[start] + v[end]의 값이 현재 탐색중인 수와 같다면 start와 end가 현재 탐색중인 수의 인덱스와 같은지 확인을 한 뒤, 인덱스가 같다면 start를 증가, end를 감소 시켜 다른 수끼리의 합도 현재 탐색중인 수와 같은지 판단한다. 그렇다면 답을 1씩 증가시킨다.

 

v[start] + v[end]의 값이 현재 탐색중인 수보다 작다면 작은 값의 start 인덱스를 증가시켜서 작은 값의 범위를 키워준다.

혹은 크다면 큰 값의 end 인덱스를 감소시켜서 큰 값의 범위를 줄여준다.

 

Code

#include<bits/stdc++.h>

using namespace std;

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

    int n, ans = 0;
    vector<int> v;

    cin >> n;

    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        v.push_back(input);
    }

    sort(v.begin(), v.end());

    for(int i = 0; i < n; i++) {
        int num = v[i];
        int start = 0, end = n - 1;

        while(start < end) {
            int sum = v[start] + v[end];

            if(sum == num) {
                if(start == i) start++;
                else if(end == i) end--;
                else{
                    ans++;
                    break;
                }
            } else if(sum < num) {
                start++;
            } else {
                end--;
            }

        }
    }

    cout << ans << "\n";


    return 0;
}

1253번: 좋다