[백준] 1253번 - 좋다

1. 문제 이해

N개의 수 중에서 다른 수 2개의 합으로 나타낼 수 있는 수의 개수를 세야 한다.

 

즉, A = B + C 를 만족하는 A의 개수를 구한다. ( 단, A != B && B != C && B != C )

 

---

2. 문제 풀이

주어진 N의 범위는 (1 ≤ N ≤ 2,000)

주어지는 수의 범위는 절댓값 10억 이하이므로, INT32 범위를 벗어나지 않는다.

 

A = B + C 인 A를 구하기 위해, 서로 다른 B와 C를 구해야 한다. B와 C는 투포인터로 구할 수 있다. 이 때, 선행으로 정렬을 해야 한다. 그래야, Left, Right 어느 쪽을 줄이고 늘릴지 판단할 수 있다.

A = B + C 일 때 B를 Left 인덱스의 수, C를 Right 인덱스의 수로 정하면 A가 표현가능한 지 구할 수 있다.

 

시간복잡도는 N^2 이므로 시간초과가 걸리지 않는다.

 

 

배열 자료구조에서 Left와 Right 인덱스를 가장 왼쪽과 가장 오른쪽으로 초기화 한다.

 

10
1 2 3 4 5 6 7 8 9 10

입력값이 위와 같은 경우, Left = 0, Right = 9 이다.

 

만약 '6'이란 수가 서로 다른 두개의 합으로 나타낼 수 있는지 구하기 위해 Left 와 Right를 바꿔가면서 찾는다.

 

초기 Left, Right 값에 의하면 num[0] + num[9] 이므로 둘의 합은 11이다. 11은 6보다 크므로 RIght를 줄여 합을 줄인다.

만약 합이 Key값, 즉 6보다 작다면 Left를 늘려 합을 늘릴 수 있다.

 

이 때, Left와 Right는 같아 질 수 없고 Left와 Right의 값은 6의 인덱스가 될 수 없다.

 

예를 들어 입력값이

5

0 1 2 1 1

이고 , 구하고자 하는 A가 2이라면 2 = 0 + 2 가 되어서는 안된다.

 

 

혹은 이분탐색으로 풀 수 있다.

A = B + C 일 때, A - B = C라고 하자.

A와 B를 2차원 배열로 표현하고, C를 이분탐색으로 찾는다. A와 B는 N^2 만큼 시간이 걸리고, 이분탐색 시간은 LogN이다. 그러므로 시간복잡도는 N^2 LogN 이므로 시간초과가 걸리지 않는다.

그러나, A,B,C는 모두 다른 수이므로 예외처리를 해줘야 한다!

---

3. 제출 결과

---

4. 문제 코드

#include <iostream>
#include <algorithm>
using namespace std;
int num[2002];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        cin >> num[i];
    }
    sort(num, num+n);
    int cnt = 0;
    for(int i=0; i<n; i++) {
        int left = 0, right = n-1;
        int key = num[i];
        
        while(left < right) {
            if(left == i) { left++;}
            else if (right == i) { right--;}
            else if (key > num[left] + num[right]){left++;}
            else if (key == num[left] + num[right]) {
                cnt++; break;
            } else { right --;}
        }
    }
    cout << cnt;
}