옥토끼는 통신교육을 풀어라( BOJ 17838 )

문제 : https://www.acmicpc.net/problem/17383

17383번: 옥토끼는 통신교육을 풀어라!!

 

문제 파악하기

옥토끼가 N개의 문제를 푸는데 필요한 시간 간격의 최댓값이 가장 작아지는 경우를 구하는 문제입니다. 옥토끼는 한 번에 2개의 문제를 풀 수 있으며, 선택한 문제는 끝까지 해결한다고 합니다. 입력된 예시(3 4 5 9 10 14 15)를 보면서 문제를 자세히 이해해보겠습니다. 만약 가장 단순하게 입력된 순서대로 문제를 선택해서 해결한다면 아래와 같은 결과가 나오게 됩니다.

A

3(3초)

5(8초)

10(18초)

15(33초)

B

4(4초)

9(13초)

14(27초)

 

이 경우 문제를 해결한 시간은 { 3초, 4초, 8초, 13초, 18초, 27초, 33초 } 가 되며, 간격의 최댓값은 9가 됩니다. 아쉽게도 주어진 입력에 대해 9라는 값는 가장 효율적인 값이 아닙니다. 그렇다면 문제를 해결하기 위해서는 어떤 방법을 선택할 수 있을까요?

 

문제 해결하기

이런 문제는 가장 간단한게 해결하는 방법부터 생각해볼 필요가 있습니다. 우리가 구해야 할 값은 시간 간격의 최댓값입니다. 이 값을 이제부터는 d라고 정의하겠습니다. 우리는 d의 값을 가장 단순하게 구하는 방법으로 1부터 하나씩 적용해보는 방법을 떠올릴 수 있습니다. 좋은 방법이지만 2가지 의문점이 떠오릅니다.

 

첫 번째, 문제를 d만큼의 간격을 두고 모두 해결할 수 있는지 어떻게 구할 수 있을까? 이는 가장 시간이 오래 걸리는 문제와 적게 걸리는 문제를 한 쌍으로 만들면 해결할 수 있습니다. 옥토끼는 한 번에 2개의 문제를 풀 수 있으니 일단 한 문제는 길게 걸리는 문제로 선정하고, 나머지는 짧게 걸리는 문제로 선정할 수 있습니다. 그리고 여기서 중요한 점은 최대한 짧게 걸리는 문제를 늦게 풀어야 합니다. 우리가 원하는 건 모든 문제를 가장 빠르게 해결하는 것이 아닙니다. 해결한 문제 사이의 간격이 가장 짧아야 합니다. 따라서, 우리는 짧게 걸리는 문제를 최대한 천천히 풀면서 길게 걸리는 문제를 해결할 시간을 벌 수 있습니다. 만약 최대한 시간을 벌어도 d만큼의 시간으로 부족하다면 우리는 d만큼의 시간 간격으로는 문제를 해결할 수 없다는 걸 유추할 수 있습니다. 이렇게 d에 대해 하나씩 시뮬레이션을 돌려보면 우리는 d의 최솟값을 구할 수 있습니다. 

 

문제를 해결했다고 생각할 수 있지만 여기서 두 번째 의문점이 떠오를 수 있습니다. 1부터 숫자를 하나씩 확인하면 제한시간 안에 정답을 구할 수 있을까? 사실 1부터 하나씩 확인하면 당연히 제한 시간 안에 해결할 수 없습니다. 하지만 우리는 d의 값에 따른 결괏값이 어떻게 변화하는지 생각해보면 어렵지 않게 문제를 해결할 수 있습니다. d의 값에 따라 우리는 [ 가능/불가능 ] 이라는 결과를 얻을 수 있으며, 이 값은 d의 크기에 영향을 받습니다. d의 값은 정답이 되기 전까지는 항상 [ 불가능 ]입니다. 그리고 정답에 도달한 순간부터 항상 [ 가능 ]으로 바뀌게 됩니다. 그리고 이런 경우에는 이분 탐색을 활용할 수 있습니다. 이분 탐색을 통해 현재 값의 결과를 토대로 탐색의 범위를 줄이면 아무리 넓은 범위라도 효율적으로 정답을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#define SWAP(a,b)(a=a^b, b=a^b, a=a^b)
using namespace std;
 
typedef long long INT;
 
int N, t, ll, rr, f;
vector< INT > inp;
 
INT l, r, mid;
INT a, b;
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &t);
        inp.push_back(t);
    }
 
    sort(inp.begin(), inp.end());
 
    l = 1; r = 1e9;
    while(l<=r) {
        // mid는 문제를 푸는데 걸리는 틈
        mid = (l+r)/2;
 
        // 오래 걸리는 문제부터 풀기 >> a
        // 오래 걸리는 문제가 풀리기 전까지 빨리 걸리는 문제 풀기 >> b
        // 값은 항상 mid의 배수로 저장하기
        a = ((inp[N-1] + (mid-1))/mid)*mid;
        b = 0;
 
        f = 1;
        ll = 0;
        rr = N-2;
        while(ll<=rr and f) {
            if(a-b == mid) {
                SWAP(a, b);
 
                a += ((inp[rr] + (mid-1))/mid)*mid;
                rr--;
            }
            else {
                if((inp[ll] + (mid-1))/mid > 1) f = 0;
                else {
                    ll++;
                    b += mid;
                }
            }
        }
 
        if(!f or a-b>mid) l = mid+1;
        else r = mid-1;
    }
 
    printf("%lld", l);
}
/*
3
1 1 10
ans: 4
*/

후기

그리디 알고리즘과 이분 탐색(매개 변수 탐색)이 결합된 문제입니다. 매개 변수 탐색 기법이 적용된 문제는 항상 흔적을 남기기 마련인데 이 문제 역시 얼추 예상할 수 있었던 문제입니다. 다만 결과를 도출하는 과정에서 그리디 알고리즘이 필요하기에 마냥 쉽다고 할 수 없는 문제였습니다. 그리디 알고리즘을 연습하는 사람에게 추천하고 싶은 문제입니다.