건조(더블릿 10F)

문제

겨울에 빨래 한 후 옷을 말리는 것은 힘든 작업이다.

그러나 제인은 매우 깔끔한 성격이라 이 지루한 작업을 싫어하지 않는다. 그녀는 라디에이터를 이용해서 이 작업을 더 빨리 하기로 하였다. 그러나 라디에이터가 작아서 한 번에 한 벌의 옷만을 말릴 수 있다.

제인은 가능한 빠른 시간안에 모든 옷을 말리기를 원한다. 당신에게 젖은 옷들이 주어질 때 모든 옷을 말리는데 필요한 가장 빠른 시간을 계산 해 줄 것을 요청했다.

제인은 빨래 후 젖은 n 벌의 옷이 있다. 각 옷은 ai 만큼의 물을 머금고 있다. 매 분당 각 옷의 물의 양은 1 만큼 준다.(물론 , 옷이 아직 완전히 마르지 않은 상태에서 )

물의 양이 제로가 될 때 옷이 완전히 말려진 것이다.

매 분당 제인은 하나의 옷을 라디에이터에 말리기 위해서 선택할 수 있고, 라디에이터는 매우 뜨거워서, 매분 물의 양이 k 만큼 준다. 물의 양은 0 미만이 될수 없고 이 경우 물의 양은 0 이 된 것이다.

일은 라디에이터를 효과적으로 이용해서 옷 말리는 시간을 줄여야 하는 것이다. 옷 말리는 작업은 모든 옷을 말릴 때까지 계속 된다.

입력

• 첫 라인은 정수 n 이 주어진다. (1 ≤ n ≤ 100 000).
• 두 번째 줄에는 ai 가 주어진다.(1 ≤ ai ≤ 109)
• 세 번째 라인은 k 가 주어진다.(1 ≤ k ≤ 109).

출력

모든 옷을 말리는 데 필요한 최소 시간을 출력한다.

해설

처음에는 우선순위큐로 간단히 풀 수 있을거 같아서 우선 순위 큐로 풀어봤다.

int main(void)
{
    int size;
    cin>>size;
    int k,temp;
    int time = 0;
    priority_queue<int> pq;
    for(int i = 0 ; i < size ; i ++){
        cin>>temp;
        pq.push(temp);
    }
    cin>>k;
    while(pq.top() > time){
        int t = pq.top();
        pq.pop();
        t = t - k + 1;
        time++;
        pq.push(t);
    }
    cout<<time<<endl;
}

결과는 input이 적을때는 답이 맞았는데 input이 많아지니 시간초과가 발생했다.

도저히 못 풀겠어서 답을 찾아봤다.

푸는 방법은 binary serch를 이용한 방법

paramathric search  참조

그것을 보고 다시 짠 코드가

vector<int> laundry;
int k;

bool check(int time){
    int cnt = 0;
    for(int i = 0 ; i < laundry.size() ; i++){
        if(laundry[i] > time) {
            cnt += ceil((double)(laundry[i] - time) / k);
        }
        if(cnt > time) return false;
    }
    return true;
}


int main(void){
    int size;
    cin>>size;
    int temp;
    int min = 1;
    int max = -1;
    for(int i = 0 ; i < size ; i ++){
        cin>>temp;
        if(temp >= max)  max = temp;
        laundry.push_back(temp);
    }
    cin>>k;
    if(k == 1) {cout<< max;return 0;}
    k--;
    int mid;
    int ans;
    while(min <= max){
        mid = (min + max) / 2;
        if(check(mid)){
            max = mid - 1;
            ans = mid;
        }
        else{
            min = mid + 1;
        }
    }
    cout<<ans<<endl;
}

여기서 제일 이해안되는게 k에서 값을 1을 왜 빼줘야하는가 였다.

이유는 자연건조와 라디에이터 건조가 동시에 안되서 이다.

자연건조가 분당 1씩은 되므로 모든 빨래는 time만큼 빠지는것을 기본으로 한다.

근데 예외가 있다. 바로 라디에이터를 이용하는 경우

라디에이터를 이용한경우에는

time + K(라디에이터가 분당 없에는 물의 양) X T(라디에이터 이용 횟수) - T(라디에이터 이용시는 자연건조가 안되므로 횟수만큼 time에서 제외 시켜주어야 한다)

이런 괴랄한 식이 나온다.

저런 괴랄한 식을 한 빨래에만 적용시키면 괜찮은데 라디에이터는 시간에 따라서 가장 큰 물을 가진 빨래를 말려야하므로

매 분마다의 진행 상황을 알아햐 한다. (난 이걸 구현하려다가 계속 에러가 발생해서 포기했다..)

답은 반대로 생각한는것이었다.

K값은 최소 1이상이다. 그러므로 모든 빨래에서 time만큼을 빼주고 라디에이터로 말리는 양을 K - 1로 하는것이다.

(결국 time값이 라디에이터를 이용하는 횟수 이므로)

이렇게 할 경우 위의 괴랄한 식을 안쓰고도 간단하게 check 함수를 구현 할 수 있다.

github : https://github.com/ji3427/algorithm/blob/master/week1/dov_10_drying.cpp