백준 1253 - 좋다

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 수가 주어졌을 때, i번째 수를 i번째 수가 아닌 다른 두 수의 합으로 표현할 수 있는 수의 개수를 구하는 것이다.

 

해당 문제는 i번째 수를 목표로 설정하고 투 포인터를 이용하여 해결할 수 있다.

보통의 경우, 정렬을 진행한 후 i번째 수를 구한다고 생각하면 i보다 작은 수의 합으로 구할 수 있기 때문에 [0, i-1]의 범위만 검사하면 된다.

하지만, 해당 문제는 입력에 음수가 포함되어 있다.

따라서, i번째 수보다 큰 수와 음수의 합으로 i번째 수를 만들 수 있는 경우가 생긴다.

따라서, [0, N-1]의 범위를 탐색해야 한다.

또한, 그중, i번째 수를 포함하지 않아야 하기 때문에 이에 대한 예외처리를 해주면 문제는 쉽게 풀 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);  

    cin >> N;

    vector<int> nums(N);

    for (int i = 0; i < N; i++)
    {
        cin >> nums[i];
    }

    sort(nums.begin(), nums.end());

    int ans = 0;

    for (int i = 0; i < N; i++)
    {
        int target = nums[i];
        int left = 0;
        int right = N - 1;

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

        while (left < right)
        {
            long long sum = nums[left] + nums[right];

            if (sum == target)
            {
                ans++;
                break;
            }
            else if (sum < target)
            {
                left++;
                if (left == i) left++;
            }
            else
            {
                right--;
                if (right == i) right--;
            }
        }
    }

    cout << ans;

    return 0;
}

---