[BOJ / C++] 백준 1253 좋다

문제

https://www.acmicpc.net/problem/1253

 

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

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

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

입력

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

 

출력

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

 

---

풀이

처음에는 두 수를 뽑아서 더한 값을 set에 전부 넣어두고 브루트포스를 시도했다.

하지만 O(N^2 * logN (set 검색))의 시간 복잡도 때문인지 시간 초과가 떴고, 투포인터를 사용해서 풀기로했다.

 

 

문제의 핵심 조건은 아래와 같다.

• 어떤 수 c = a + b로 반드시 c!=a, c!=b를 만족
• 단, 수의 위치가 다르다면 값이 같아도 다른 수이다. 
• ex) [0, 0, 0, 0] -> 일 때 답은 4이다.

 

따라서 값이 같은지를 확인하는게 아니라, 인덱스가 다른지를 확인하는 조건을 추가한다.

 

투포인터는 left는 오른쪽으로, right는 왼쪽으로 가면서 두 포인터가 만나기 전까지 탐색하는 방식이다.

따라서 인덱스가 같은 경우, left, right를 조정하는 코드가 필요하다.

 

또한 수의 범위가 더했을 때 int 범위를 벗어날 수 있으므로 long long 타입으로 진행했다.

 

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

int main() {
    int n, ans = 0;
    cin >> n;
    vector<long long> nums(n, 0LL);

    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());

    // 투포인터
    for (int i = 0; i < n; i++) {
        int left = 0, right = n - 1;

        // 각 수의 포인터가 만나기 전까지 탐색
        while (left < right) {
            // 찾으려는 수와 같은 인덱스라면 조정
            if (left == i) {
                left++;
                continue;
            }
            if (right == i) {
                right--;
                continue;
            }

            // 두 수의 합이 찾으려는 수와 같다면 good
            long long sum = nums[left] + nums[right];
            if (sum == nums[i]) {
                ans++;
                break;
                // 값이 더 크다면 오른쪽 포인터 이동
            } else if (sum > nums[i]) {
                right--;
            } else {
                // 값이 작다면 왼쪽 포인터 이동
                left++;
            }
        }
    }
    cout << ans;

    return 0;
}