[백준] 1253 좋다

1253번: 좋다

문제 확인

 

map, set을 이용해 해쉬로 풀어도 되지만 느리므로 투 포인터 알고리즘으로 풉니다.

 

풀이

 

2개의 수를 잡아서 어떠한 수를 만들 수 있는지 확인하는 방식은  O(N^2), 하나의 수를 잡고 이 수를 만들 수 있는지 확인하는 방식 또한 O(N^2)지만 전자의 경우 그 수가 배열 안에 있는지 확인해야 하는 작업이 필요하므로 더 많은 시간이 필요합니다.

 

투 포인터 알고리즘을 사용하기 위해 먼저 정렬을 합니다.

그 후 두 포인터를 0, n-1에 두고 현재 확인할 수를 i : 0~n-1로 둡니다. 두 포인터의 값을 더한 수가 현재 수와의 대소 비교를 경우의 수로 둡니다. 정렬을 하였기 때문에 right--는 합이 줄어들게 되고 left++은 합이 늘어나게 됩니다.

1. left + right < ary[i] : 정렬을 해 두었기 때문에 left++ 해 줍니다.
2. left + right > ary[i] : right--
3. left + right == ary[i] : 두 수를 더해 다른 수를 만들어야 하므로 예외처리를 해 주고 결과를 반영합니다.

 

코드

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int main() {
    int ary[2000];
    int n, res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &ary[i]);
 
    sort(ary, ary + n);
    for (int i = 0; i < n; i++) {
        int left = 0, right = n - 1;
        while (left < right) {
            if (ary[i] > ary[left] + ary[right]) left++;
            else if (ary[i] < ary[left] + ary[right])right--;
            else {
                if (left == i) left++;
                else if (right == i) right--;
                else {
                    ++res;
                    break;
                }
            }
        }
    }
    printf("%d", res);
}