백준 - 17383 옥토끼는 통신교육을 풀어라!!

[Platinum IV] 옥토끼는 통신교육을 풀어라!! - 17383

문제 링크

성능 요약

메모리: 2412 KB, 시간: 24 ms

분류

이분 탐색, 그리디 알고리즘, 매개 변수 탐색

제출 일자

2024년 4월 8일 19:09:36

문제 설명

UCPC World Finals 2020을 준비하는 옥토끼는 여름학교에 가기 위하여 통신교육 문제를 푼다. 그러나 악덕 조교 tncks0121은 옥토끼가 오랫동안 문제를 풀지 않으면 '옥통풀'을 외치며 독촉한다.

옥토끼는 N개의 문제를 모두 풀어야 하며 각 문제를 푸는 데 T_i분이 걸린다. 옥토끼는 멀티태스킹 능력이 발달하여 한 번에 동시에 두 개의 문제를 풀 수 있다. 모든 문제는 정수 시각에 풀기 시작해야 하며 한 번 풀기 시작한 문제는 도중에 풀이를 중단하지 않는다. 옥토끼가 항상 문제를 풀고 있을 필요는 없으며 문제를 푸는 순서에는 제약이 없다.

tncks0121은 옥토끼가 문제를 해결한 시점만 볼 수 있을 뿐, 옥토끼가 지금 문제를 풀고 있는지 쉬고 있는지 모른다. 문제 하나를 풀고 나서 다음 문제를 풀기까지 걸리는 시간이 길어지면 tncks0121의 독촉이 심해지기 때문에, 옥토끼는 이 간격의 최댓값이 최소가 되도록 계획을 세워 모든 문제를 풀려고 한다. 옥토끼를 도와 문제를 푸는 전략을 짜는 프로그램을 작성하여라. tncks0121은 통신교육이 시작되자마자 독촉을 시작하므로, 옥토끼가 첫 문제를 푸는 데 걸리는 시간도 고려해야 함에 유의하여라.

입력

첫 번째 줄에는 문제의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

두 번째 줄에는 옥토끼가 각 문제를 푸는 데 걸리는 시간 T_i (1 ≤ T_i ≤ 10⁹, T_i는 정수)가 주어진다.

출력

첫 번째 줄에 옥토끼가 문제 하나를 풀고 나서 다음 문제를 풀기까지 걸리는 최대 시간의 최솟값을 출력한다.

풀이과정

너무 어려웠던 문제...
처음에는 그리디하게 접근하는 부분에서 문제의 시작시간과 끝시간을 두고 풀려고 했으나 구현을 하지 못했다. 또 이 풀이에서의 다른 문제점은 주어진 시간 내에 특정 길이의 통신문제를 찾을 수가 없다는 것이었다.

파라메트릭 서치라는 감은 있었지만 그리디하게 접근하는 부분을 해결하지 못해서 다른 사람의 풀이를 참고했다.

이 문제는 크게 두 부분으로 나뉜다.

1. 해를 찾기(조건에 따라서 범위를 좁혀나감)

-> 파라메트릭 서치
2. 조건 설정하기
-> 그리디

해를 찾기

파라메트릭 서치로 해를 찾기 위해서 범위를 설정해준다.
우선 입력되는 문제들의 시간을 배열에 저장해서 정렬해준다.

범위 설정

가장 적은 시간이 걸리는 문제가 파라메트릭 서치의 low 범위가 되고, 가장 오랜 시간이 걸리는 문제가 파라메트릭 서치의 high 범위가 된다. 문제의 풀이 시간은 10^9 이하이므로, int 범위 내에서 탐색이 가능하다. (10^9 + 10^9 = 2 * 10^9 < 2,147,483,647 이므로)

해는 low와 high 사이에 존재한다. 조건에 따라서 해의 범위를 좁혀주기만 하면 된다.
low가 high 보다 작은 동안에 반복문이 실행되므로 해는 하나로 결정된다.

조건에 따른 범위 조정

구해야하는 해는 최소값을 만족해야하므로, 중간값 m에 대해서 조건을 만족하는 경우 high를 줄여주고(시간 줄이기), 만족하지 못하면 low을 늘려준다(시간 늘리기).

    for (int i = 0; i < N; i++) cin >> arr[i];

    sort(arr, arr + N);

    int l = arr[0], r = arr[N - 1], m = 0;
    while (l < r) {
        m = (l + r) / 2; 
        if (chk(m)) r = m;
        else l = m + 1;
    }

코드에서 l = low 범위, r = high 범위.

조건 설정하기

이 문제에서 제일 어려운 부분이다. 매개변수 m을 받는 bool 함수를 짜준다. 모든 문제를 최대 m의 시간 간격 내에 풀 수 있다면 조건을 만족하게 된다. 만족할 경우 true를 반환하고 그렇지 못하면 false를 반환한다.

첫번째 문제에 대한 조건

정렬된 문제들에 대해서 가장 앞에 있는 문제는 가장 짧은 문제로 이 문제를 푸는 시간이 m보다 크다면, 조건을 만족하지 못한다.
그러므로 arr[0] > m 이라면 false를 반환한다.

나머지 문제에 대한 조건

첫번째 문제를 m 이내에 풀 수 있다면 1번 ~ N-1번 문제에 대해서 확인한다.

1. 어떤 문제가 m 이내에 풀린다면 m 초과의 시간에 풀리는 다른 문제들의 앞에 배치하여 문제 풀이의 시간 간격을 줄일 수가 있다.
2. 만약 n*m(n>=2)의 시간 내에 문제가 풀린다면 해당 문제 앞에 m 이내에 풀리는 문제를 배치할 수 있는지 확인한다.

예시

arr[] = {3,4,5,9,10,14,15}, m = 5라고 가정하자.
그리고 m 이내에 풀리는 문제의 갯수를 cnt라고 하자.

0번 문제
=> 3 < 5 이므로 조건을 만족한다. 나머지 문제들에 대해서 확인한다.
1번 문제
=> 4는 1m 안에 끝난다. 그러므로 카운트 해준다. cnt = 1
2번 문제
=> 5는 1m 안에 끝난다. 그러므로 카운트 해준다. cnt = 2
3번 문제
=> 9는 2m 안에 끝난다. 해당 문제 앞에는 m의 간격을 메울 다른 문제가 배치되어 있어야 한다. 항상 0번 문제가 제일 앞에 배치되므로 cnt의 감소 없이 문제를 해결할 수 있다.
4번 문제
=> 10은 2m 안에 끝난다. 해당 문제 앞에는 m의 간격을 메울 다른 문제가 배치되어 있어야 한다. 3번 문제가 4번 앞에서 풀렸으므로, cnt의 감소 없이 문제를 해결할 수 있다.
5번 문제
=> 14는 3m 안에 끝난다. 해당 문제 앞에는 2m의 간격을 메울 다른 문제가 배치되어 있어야 한다. 4번 문제가 5번 앞에서 풀렸으므로 m의 간격이 없어졌으나, 나머지 m의 간격이 존재한다. 이 때 cnt의 문제를 하나 배치시킨다. cnt = 1
6번 문제
=> 15는 3m 안에 끝난다. 해당 문제 앞에는 2m의 간격을 메울 다른 문제가 배치되어 있어야 한다. 5번 문제가 6번 앞에서 풀렸으므로 m의 간격이 없어졌으나, 나머지 m의 간격이 존재한다. 이 때 cnt의 문제를 하나 배치시킨다. cnt = 0

-> 모든 문제는 최대 5의 간격 이내에 해결될 수 있다.

일반화

첫번째 문제를 풀 수 있는지 확인했다면, 나머지 문제에 대해서 다음을 확인한다.

문제가 m 이하의 시간에 풀리게 되는 경우에는 cnt를 해주고,
m 초과의 시간에 풀리게 되는 경우에는 n*m 이내의 시간에 풀리는 지에 대한 n을 계산한다.

원래대로라면 총 n-1개의 간격을 채워야 한다. 하지만 동시에 두 개의 문제를 해결할 수 있으므로 항상 1개의 간격은 자동으로 채워진다.
그러므로 총 n-2개의 간격만 채우면 된다.

만약 n-2 > cnt 라면 간격을 채울 수 있는 m 이하의 문제들이 부족하게되어 모든 문제를 최대 m의 간격에 해결할 수 없다. 이 때 false를 리턴한다.

n-2 <= cnt 라면 cnt에서 n-2를 빼주고 다음 문제를 계속 반복한다.
모든 문제가 해결된다면 true를 리턴한다.

정렬된 문제들에 대해서 선형 시간 이내에 조건을 확인할 수 있다.

코드

acc는 설명에서 cnt에 해당하고, cur는 설명에서 n-2에 해당한다.

#include <iostream>
#include <algorithm>
#define MX 100005
using namespace std;
int N, arr[MX];
bool chk(int x) {
    if (arr[0] > x) return 0;
    int acc = 0, cur = 0;
    for (int i = 1; i < N; i++) {
        if (arr[i] <= x) {
            acc++;
            continue;
        }
        cur = arr[i] / x + (arr[i] % x ? 1 : 0) - 2;
        if (cur > acc) return 0;
        acc -= cur;
    }
    return 1;
}
int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
    sort(arr, arr + N);
    int l = arr[0], r = arr[N - 1], m = 0;
    while (l < r) {
        m = (l + r) / 2; 
        if (chk(m)) r = m;
        else l = m + 1;
    }
    cout << r;
}