[BOJ 1253 // C++] 좋다

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1253번 문제인 좋다이다.

문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1253

1253번: 좋다

이 문제는 2-sum problem 의 변형으로 볼 수 있다.

2-sum problem은 정수의 배열 arr과 어떤 수 target이 주어졌을 때 그 수를 배열의 (distinct한) 두 index에 있는 수의 합으로 나타낼수 있는지를 묻는 문제이다. 2-sum problem은 대표적인 투포인터 문제로, 자세한 내용은 나중에 따로 다루겠다.

 

이 문제를 풀 때 유의해야할 점은 target을 배열에서 뽑아왔다는 것이다. 즉, 합하는 두 수의 index는 target과도 달라야한다. 예를 들어, 0 0 2 2 라는 배열을 살펴보자. 두 2는 다른 index에 있는 2와 0 하나의 합으로 표현이 가능하니 좋다(GOOD)고 할 수 있다. 하지만 두 0은 자기자신을 제외한 두 수의 합으로 0을 만들 수 없다. (자기 자신을 포함한다면 가능하다.) 글쓴이는 이 문제를 포인터 중 하나가 target을 가리킨다면 다음 index로 넘기는 방식으로 해결했다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int nums[2000];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; // 배열 읽어오기
    int x;
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> x;
        nums[i] = x;
    }
    sort(nums, nums + n); // 배열 정렬하기
    int ans = 0; // ans: 다른 두 수의 합으로 나타낼 수 있는 수의 개수
    for (int i = 0;i < n;i++) { // 각 수(nums[i])에 대한 반복문
        int target = nums[i];
        int leftpt = 0; // 포인터 정의
        if (leftpt == i) leftpt++; // 예외처리 - 합으로 나타내려는 수와 겹치는 index
        int rightpt = n - 1;
        if (rightpt == i) rightpt--;
        while (rightpt > leftpt) { // 투 포인터 구현
            int currentsum = nums[leftpt] + nums[rightpt];
            if (currentsum == target) {
                ans++;
                break;
            }
            else if (currentsum > target) {
                rightpt--;
                if (rightpt == i) rightpt--; // 예외처리 - 합으로 나타내려는 수와 겹치는 index
            }
            else {
                leftpt++;
                if (leftpt == i) leftpt++;
            }
        }
    }
    cout << ans;
    
    return 0;
}