좋은 수 구하기(백준 1253)

1. 문제이해 

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

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

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

 

(|Ai| ≤ 1,000,000,000, Ai는 정수) -> 음의 정수, 0도 포함

 

예시1) N=3 일때 3, 2, 5 

어떤 수가 3일때 다른 두 수 2 + 5의 조합으로 나타내지 못함

어떤 수가 5일때 다른 두 수 3 + 2의 조합으로 나타낼 수 있으니까 좋은 수로 판단

 

예시2) N=2 일때 0, 0

어떤 수가 0일(첫번째 있는 0)때 다른 두 수가 없으므로 조합을 만들 수 없음

자기자신을 포함해서 조합을 만들 수 있지만 자기자신이 어떤 수에 포함되는 경우에는 최소 3개 이상의 수가 있어야지 조합을 만들 수 있음

 

예시3) N=5 일때 0, -1, -1, 1, 1

두번째 있는 -1을 어떤 수로 지정하고 조합을 만들면 0과 -1(3번째 -1)로 만들 수 있는데 -1의 경우 위치가 다르기 때문에 좋은 수를 만들 수 있음

 

2. 문제분석 

1. 작은 수 부터 오름차순 정렬

 

2. 수가 3개 이상인 경우부터 조합을 만든다. 

(수가 2개 이하이면 자기자신을 제외하고 다른 두 수의 합을 만들 수 없음)

 

3. 좋은 수(K)를 첫번째에 있는 값부터 마지막에 들어있는 값까지 순서대로 적용

 

4. 좋은 수(K)로 지정할때마다 투 포인터(커서) 개념을 사용

시작 포인터는 배열의 첫 인덱스로 지정하고 끝 포인터는 맨 마지막 인덱스로 지정

 

ex) N=4 일때 1, 1, 2, 5 

4.1. 두 개의 포인터가 가리키는 값을 더해서 K가 되는 경우

두 개의 포인터가 가리키는 값을 더해서 K와 동일하면 다음 좋은수로 변경 

두 개의 포인터가 가리키는 값을 더해서 K와 동일하지만, K가 두 개의 포인터에 속하는 경우 좋은 수가 아니기 때문에 K가 시작 포인터라면 시작 포인터 인덱스를 1증가 시키고 끝 포인터라면 1감소 시킨다. 

 

4.2. 두 개의 포인터가 가리키는 값을 더해서 K가 아닌 경우

두 개의 포인터가 가리키는 값의 합이 K보다 작은 경우 시작 포인터의 위치를 다음 인덱스로 1증가

(K값보다 작으니까 맞추기 위해서 값을 증가시킴)

두 개의 포인터가 가리키는 값의 합이 K보다 큰 경우면 끝 포인터의 위치를 이전 인덱스로 1감소

(K값보다 크니까 맞추기 위해서 값을 감소시킴)

 

5. 시작 포인터의 위치와 끝 포인터의 위치가 동일하거나 서로 엇갈릴 때까지 조합을 찾음

 

3. 코드

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

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

    // 1.입력
    int N;     
    cin >> N;
    int* num = new int[N]; // N개의 수
    for (int i = 0; i < N; i++) {
        cin >> num[i];
    }

    // 2.작은 수부터 오름차순 정렬 
    sort(num, num + N);    
    int count = 0; // 좋은 수의 개수

    if (N >= 3) {
        for (int i = 0; i < N; i++) {
            int goodNum = num[i];
            int s = 0; // 시작 커서
            int e = N - 1; // 끝 커서
            while (s < e) {
                if (num[s] + num[e] == goodNum) {
                    if (s != i && e != i) {
                        count++;
                        break;
                    }
                    else if (s == i) {
                        s++;
                    }
                    else if (e == i) {
                        e--;
                    }
                }
                else if (num[s] + num[e] > goodNum) {
                    e--;
                }
                else if (num[s] + num[e] < goodNum) {
                    s++;
                }
            }
        }
    }
    
    
    cout << count;
           
    
    return 0;
}