[platinum2] [해설안봄,분류안봄] 1088 케이크

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

우연찮게 분류로 문제를 찾지 않았는데도 재밌어 보이는 문제를 풀다보니 그리디 + 우선순위큐 조합 문제를 계속 풀게 되었다.

이 문제도 효율적으로 소사기, 그리디컵과 같은 종류이지만 발상은 또 전혀 다른 문제였다.  그리디 문제는 항상 문제가 신박한 것 같아서 재밌다.

 

이문제를 풀기 위해선 한 개의 조각을 어떻게 가장 최선으로 자를 수 있을지 생각 해봐야 한다.

이렇게 한 조각이 3, 5 일때  5인 조각을 2,3으로 나누면  |c - a| 값은 최소가 되지만 |b-a| 값은 그렇지 않다.  b,c조각으로 나눴을 때 c가 길이차이가 0이 되게 맞추면 다른 한쪽인 b는 길이차이가 벌어진다. 따라서  균등하게 잘라야 조각의 차이가 최소가 될 거라는건 어렵지 않게 생각할 수 있다.

이건 길이가 k인 조각을 n등분 할 때, 한 조각의 길이가 k / n 이 되어야 한다는 것으로 일반화 할 수 있다.

 

그렇다면 이제 M번을 어떻게 자를까?

그리디를 풀때는 가장 큰 값 또는 가장 작은값 부터 생각해야 발상이 잘 생각난다.

현재 가장 큰 길이와 가장 작은 길이는 7,3 이므로 차이는 4이다. 여기서 한번을 잘라야 한다고 하면 길이가 가장 큰 7을 잘라야 할 것이다. 7말고 다른 조각을 잘라봤자 계속 가장 큰 길이는 7이므로, 구하려는 값(가장 큰길이 - 가장 작은 길이) 를 늘리면 늘렸지 (자르다가 가장 작은 길이를 줄이는 경우) 줄일 수는 없을 것이다. 

 그러므로 당연히 7을 잘라야 하고, 1번 잘랐을 때는 3.5 가 된다. 

이렇게 자르고 나면 가장 큰 길이는 6이 된다.  이때도 마찬가지로 6말고 다른 걸 자르게 되면 구하려는 값이 줄어들지 않을 것이므로 반드시 6을 잘라야 한다.

그 다음은 순서대로  5, 4를 자른다.

이제  7 / 2 가 가장 큰 값이므로 이 값을 줄여야 한다. 원래 값은  7이였고 한번잘라 2등분한 걸 한번 더 잘라 3등분 해야 한다.

그런데 우리는 아까 균등하게 자르는게 최선이라는 것을 알았으므로 한 번 더 자를 때  한 조각의 크기가 7 / 3이 되게 잘라야 한다.

 

그 다음은 3을 잘라야 하는데, 보다 시피 3인 조각이 2개이다. 이럴 경우엔 어떻게 해야 할까.

둘중에 어떤 걸 먼저 잘라도 상관이 없다. 그이유는 3인 조각중 어떤 걸 잘라도 다른 조각이 길이가 3인 채로 남아있어 최대값은 여전히 3이다. 따라서 이때는  최소 길이값을 더 줄여서 구하려는 값(최대값 - 최소값)  을 늘리면 늘렸지 줄일수는 없다.  길이가 3인 모든 조각이 다 잘려야 구하려는 값을 더 줄일 여지를 만들어 볼 수 있다.   따라서 같은 길이의 조각이 여러개있으면 그 조각들이 모두  잘려야 승부를 볼 수 있으므로, 그 전까진 같은 길이라면 조각을 자를 때 순서는 따질 필요는 없다.

 

두 3을 자르면 다음과 같이 된다.

이런 식으로 M번 잘라나가면서  최대값 - 최소값의 최솟값을 구하면 된다.

M번 돌릴 때 n등분된 걸 n+1등분 시켜야 하므로 poll하고 새로 값을 넣어  정렬을 해야 하기 때문에 시간복잡도는(M * logM)이 될 것이다.(우선순위큐)