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

문제

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

예제 입출력

• 예제 입력 1

1
4
9999998
1
2
9999999

• 예제 출력 1

yes 1 9999999

Solution

쉬운 문제다. 투 포인터든 이분 탐색이든 뭐든 써서 만들면 장땡인 문제.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int dst, N;
    while(cin >> dst >> N){
        vector<int> vec;
        for(int i = 0; i < N; i++){
            int input; cin >> input;
            vec.push_back(input);
        }
        sort(vec.begin(), vec.end());

        dst = dst * 10000000;
        int left = 0, right = vec.size() - 1;
        int leftAns = -1, rightAns = -1;
        while(left < right){
            int sum = vec[left] + vec[right];
            if(sum == dst){
                leftAns = vec[left];
                rightAns = vec[right];
                break;
            }
            else if (sum < dst){
                left++;
            }
            else {
                right--;
            }
        }
        
        if(leftAns == -1 || rightAns == -1) cout << "danger\n";
        else cout << "yes " << leftAns << " " << rightAns << '\n';
    }
}

일단 고려해야 할 사항은 두 가지다.
1. 테스트케이스가 몇 개인지 정해져있지 않다.
2. 너비의 단위는 센티미터로 입력되나 레고의 길이는 나노미터로 처리된다.

테스트 케이스가 정해져있지 않기 때문에 입 출력이 멈춘 시기에 반복을 멈춰야 한다.

int dst, N;
while(cin >> dst >> N)

난 이런식으로 해결했다. 두 가지 변수에 대한 입력이 없다면 더이상 프로그램을 작동시키지 않고 종료한다.

while(cin >> dst >> N){
    vector<int> vec;
    for(int i = 0; i < N; i++){
        int input; cin >> input;
        vec.push_back(input);
    }
    sort(vec.begin(), vec.end());

    dst = dst * 10000000;
    int left = 0, right = vec.size() - 1;
    int leftAns = -1, rightAns = -1;
    while(left < right){
        int sum = vec[left] + vec[right];
        if(sum == dst){
            leftAns = vec[left];
            rightAns = vec[right];
            break;
        }
        else if (sum < dst){
            left++;
        }
        else {
            right--;
        }
    }
        
    if(leftAns == -1 || rightAns == -1) cout << "danger\n";
    else cout << "yes " << leftAns << " " << rightAns << '\n';
}

투 포인터 알고리즘의 핵심은 간단하다. 언제 포인터를 옮길 것인가?
우선 입력받은 레고들을 정렬한다. 가장 빠르게, 가장 적절한 길이들을 찾기 위해서는 어떤 길이가 큰 녀석인지, 작은 녀석인 지 정리 할 필요가 있다.

그 다음부터는 흔히 아는 투 포인터다. 투 포인터에 대해 잘 모르는 사람이 있다면 MergeSort에 대해 공부 해 보면 도움이 된다.

간단하다. 가장 작은 놈과 큰놈 기준으로 하나하나 범위를 줄여가며 덧셈 값이 찾고자 하는 값과 같다면 종료하면 그만이다. 찾아지지 않는다면 결과 데이터가 갱신되지 않을테고 값을 찾지 못했다는 이야기겠지.
정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.
해당 조건으로 인해 한번 답을 찾는다면 굳이 답을 계속해서 찾을 필요는 없다.