[백준 3632번] Drying

문제 링크

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

 

문제 요약

\(N\)개의 빨래와 각각의 빨래가 가지고 있는 초기 물의 양이 주어진다. 모든 빨래는 1분마다 물의 양이 1씩 줄어들며, 매 분마다 한 개의 빨래를 선택해 라디에이터에 올릴 수 있다. 라디에이터에 올린 빨래는 물의 양이 1분마다 \(K\)씩 줄어든다. 모든 빨래의 물의 양이 0이 되는 최소한의 시간을 구하는 문제이다.

 

문제 풀이

만약 \(X\)분 내에 모든 빨래를 말릴 수 있는 방법이 존재한다면, \(X\)분보다 더 큰 시간 내에서도 모든 빨래를 말릴 수 있다. 반대로 \(X\)분 내에 모든 빨래를 말릴 수 없다면, \(X\)분 보다 더 작은 시간 내에 모든 빨래를 말릴 방법은 존재하지 않는다. 이 특성을 이용해 최적화 문제를 결정 문제로 바꿀 수 있고, 이분 탐색을 이용해 답을 빠르게 찾을 수 있다.

 

이제 \(X\)분 내에 모든 빨래를 말릴 수 있는지 확인하는 방법을 알아보자. 모든 빨래를 \(X\)분 내로 말리기 위해서는 라디에이터를 최선의 방법으로 사용해야 한다. 빨래 \(i\)가 가지고 있는 물의 양을 \(A[i]\)라고 하자. 만약 \(A[i]\)가 \(X\)보다 작거나 같다면, 이 빨래는 라디에이터를 사용하지 않아도 된다. 그러나 \(A[i]\)가 \(X\)보다 크다면, 이 빨래를 \(X\)분 내로 말리기 위해 라디에이터를 최소한의 횟수로 사용해야 한다.

 

이 경우, \(A[i]\)에서 \(X\)를 뺀 값은 라디에이터를 이용해 추가적으로 제거해야 하는 물의 양이다. 이 값을 \(K - 1\)로 나누고 올림 한 값이 이 빨래를 \(X\)분 내에 말리기 위해 필요한 최소 라디에이터 사용 횟수다. 모든 빨래에 대해 이 값을 계산한 뒤 더한 값이 \(X\)를 초과하면, \(X\)분 내에 모든 빨래를 말릴 수 없다는 뜻이다.

 

\(K\)가 1인 경우는 예외 케이스인데, \(A[i]\)가 \(X\)를 초과하면 라디에이터를 사용해도 빨래를 \(X\)분 내에 말릴 수 없으므로 불가능하다고 판단하면 된다.

 

소스 코드

#include <stdio.h>

int n;
long long k, A[100010];

bool isPossible(long long x) {
    long long tot = 0;
    
    for (int i = 0 ; i < n ; ++i) {
        if (A[i] > x) {
            if (k == 1) {
                return false;
            }
            
            long long up = A[i] - x;
            long long down = k - 1;
            
            tot += (up / down) + (up % down ? 1 : 0);
        }
    }
    
    return tot <= x;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 0 ; i < n ; ++i) {
        scanf("%lld", &A[i]);
    }
    
    scanf("%lld", &k);
    
    long long lo = 0, hi = 1e9 + 10;
    
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        
        if (isPossible(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    printf("%lld\n", lo);
}