BOJ백준 3649 로봇프로젝트 풀이(C++)

문제링크

문제는 주어진 블록 중 두개를 골라 주어진 길이의 구멍을 막을 수 있나 알아보는 문제이다.

즉, 주어진 값이 있을 때, 그 중에서 주어진 조건을 만족하는 차이가 가장 큰 값이 있는지 탐색하는 문제라고 볼 수 있다.

접근 방법은 다음과 같다.

어떠한 크기의 구멍을 두 블록으로 막는다고 했을 때 두 블록은 '반드시' 하나의 작은 블록과 하나의 큰 블록으로 이루어져 있다.

따라서 주어진 블록 값들을 오름차순으로 정렬한 뒤 각각의 끝에서부터 블록을 하나씩 골라 구멍의 값과 비교하고 다음에 따라 원하는 값을 찾을 때까지 반복한다.

-  구멍의 크기가 두 블록의 합보다 작은 경우 -> 작은 블록 쪽을 큰 쪽으로 한 칸 옮긴다(인덱스가 i였다면 i+1로 증가시킨다.)

-  구멍의 크기보다 두 블록의 합이 큰 경우 -> 큰 블록을 잔은 쪽으로 한 칸 옮긴다(인덱스가 j였다면 j-1로 감소시킨다.)

코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int W, N;
    while (scanf("%d\n%d", &W, &N) == 2) {
        vector<int> blocks(N);
        W *= 10000000;
        for(int i=0; i<N; i++) {
            scanf(" %d", &blocks[i]);
        }
        sort(blocks.begin(), blocks.end());
        
        int l = 0, r = N-1;
        while (l < r) {
            int sum = blocks[l] + blocks[r];
            if(sum == W) {
                break;
            }
            else if(sum < W) {
                l++;
            }
            else {
                r--;
            }
        }
        if(l >= r) {
            printf("danger\n");
        }
        else {
            printf("yes %d %d\n", blocks[l], blocks[r]);
        }
    }
}
 

이 문제에서 주의해야 할 점은 테스트 케이스가 여러 개라고만 하고 다른 조건을 주지 않았기 때문에 그에 대한 처리를 해주어야 한다는 것이다.

다양한 입력 방식을 처리하는 방법은 이 블로그 에서 잘 정리해놓았으므로 참고하면 좋을 것 같다.