Baekjoon 3649

1) 문제 분석

길이의 합이 x와 같은 조각 2개를 찾아내는 문제이다. 모든 원소에 대해 하나씩 비교를 해서 답을 구하는 식으로 코드를 작성하면 대략 O(n^2)의 시간복잡도가 나오며, 레고의 최대 개수가 1,000,000개이기 때문에 효율적이지 못하다. 우선 크기 순으로(오름차순)으로 정렬한 뒤에, l과 r이라는 두 변수를 이용해서 양 끝에서 한 칸씩 중심으로 이동하면서 두 원소의 합이 x와 같은 경우를 찾으면 된다. 만약 그런 경우가 없다면 l과 r은 중간에서 만나게 된다. 문제 자체는 어렵지 않았는데, 1)테스트 케이스 개수가 주어지지 않아서 입력 받는 방법 때문에 헤매고, 2) 처음에 두 원소의 합이 x보다 작을 때 까지 while 루프를 사용해서 r의 값을 감소시키는 식으로 코드를 짰는데, 이 경우 r이 아예 배열 인덱스의 범위를 벗어나는 경우를 계산하지 못하기 때문에 답이 계속 틀린 점을 찾아내지 못해 애를 먹었다. 그래서 중요한 점은, 배열에서 []로 원소를 접근할 때 인덱스가 배열의 범위를 벗어나는 경우가 발생하지 않는지 항상 확인해야 한다는 것이다.

2) 코드

#include <iostream>
#include <algorithm>

using namespace std;

int x;              //구멍의 너비
int n;              //레고 조각수
int lego[1000000];  //레고 조각들
string buffer;
bool flag;          //답 찾으면 true

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    while (getline(cin, buffer) && !buffer.empty()){
        flag = false;
        //입력
        x = atoi(buffer.c_str());
        cin>>n;
        for (int i = 0; i < n; i++)
            cin >> lego[i];
        cin.ignore();

        //크기의 오름차순으로 레고 조각 정렬
        sort(lego, lego + n);

        int l = 0;     //가장 왼쪽에서 시작
        int r = n - 1; //가장 오른쪽에서 시작
        x *= 1e7;

        //양 옆에서 한 칸씩 중간으로 이동하면서 답을 찾음
        while (l < r) {
            int sum = lego[l] + lego[r];
            //구멍에 맞는 조각 2개 찾음
            if(sum == x){
                flag = true;
                break;
            }
            else if(sum<x)
                l++;
            else
                r--;

        }
        if(flag)
            cout << "yes " << lego[l] << " " << lego[r] << "\n";
        else
            cout << "danger\n";
    }
}

문제의 코드

while (l < r) {
    while (lego[l] + lego[r] > x)
        r--;
    if (lego[l] + lego[r] == x) {
        flag = true;
        break;
    }
    l++;
}