[ 백준 1253 ] 좋다 (C++) - 투 포인터

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 일단 수가 10억까지 늘어날 수 있다. 이는 배열을 만들어서 풀면 메모리초과가 발생하니 배열로 풀 수 없는 문제이다.
2. 그러면 모든 수에 대해서 모든 경우를 더해야하나? 이것도 아니다. 2000개가 있을 때, 2000 * 2000 * 1999 / 2 라는 식을 계산해보면 40억이라는 숫자가 나온다. 따라서 모든 경우를 구하는 방법도 안된다.
3. 이런 문제를 풀어본 경험이 있다면 비교적 쉽게 풀이 방식을 찾을 수 있다. 바로 투 포인터이다.
   3-1. 배열을 입력받은 뒤 정렬한다.
   3-2. 가장왼쪽의 숫자와 가장 오른쪽의 숫자를 정한다.
   3-3. 둘의 합이 내가 구할려는 숫자보다 작으면 left++ 크다면 right--를 해준다. (오름 차순일 때, 둘의 합을 늘려준다는 의미이다.)
   3-4. 자기자신은 계산에 포함할 수 없으니 만약 left 혹은 right가 내 위치가 된다면 한번 더 옮겨준다.
   3-5. 그렇게 left 가 right 보다 같거나 커지면 구할 수 없는 수이다.(GOOD이 아닌 숫자이다.)
4. 이렇게 한단계식 늘려가거나 좁혀가면서 최적의 숫자를 구하는 방식인데, 모든 경우를 구할 필요가 없고 매번 N만큼만 구하면 된다. 따라서 최악의 경우 N*N의 경우의 수를 갖으므로 제한시간안에 통과할 수 있다.

---

⭐️ 정답 코드 및 설명

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// 5
//
// -1 0 1 2 3

int sol(vector<int> vec) {
    int left, right, sum, GOOD = 0;
    for (int i = 0; i < vec.size(); i++) {
        left = 0;
        right = vec.size() - 1;

        if (i == left) left++;
        if (i == right) right--;

        while (left < right) {
            sum = vec[left] + vec[right];
            if (sum == vec[i]) {
                GOOD++;
                break;
            }

            if (sum < vec[i]) left++;
            if (sum > vec[i]) right--;

            if (i == left)
                left++;
            else if (i == right)
                right--;
        }
    }
    return GOOD;
}

int main() {
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());

    cout << sol(vec);
    return 0;
}

---

🤔 문제 후기

투 포인터라는 개념을 알고, 이 문제가 투 포인터라는 것을 깨닫는 순간 매우 쉬운 문제였다. 자기자신이 계산에 포함되면 안된다는 예외만 처리해준다면 딱히 어려운 문제는 아니였던 것 같다.