백준 1088번 : 케이크
지민이가 가지고 있는 케이크 N조각 을 최대 M번 자를 때, 무게가 가장 많이 나가는 조각과 적게 나가는 조각의 차이를 최소화하여 그 값을 출력하는 문제이다. 이 값을 최소화하려면 잘라야하는 조각은 무게가 가장 많이 나가는 조각이다. 적게 나가는 조각을 잘라봤다 차이가 더 커질 뿐이다. 구현할 때는 deque 와 upper_bound 를 사용하여 케이크의 목록을 만들고 업데이트했다.
처음에는 가장 무거운 조각을 자를 때는 가장 가벼운 조각의 무게에 맞춰 자르려고 노력했는데 그 이유는 가장 무거운 조각과 가벼운 조각의 차이가 바로 모든 값의 범위이기 때문이다. 가장 가벼운 조각에 맞춰 자르면 범위는 필연적으로 줄어들 수 밖에 없다. 하지만 나누었을 때 어쩔 수 없이 범위가 늘어나는 경우, 반으로 나누는 게 가장 적게 늘어나서 반으로 나눈 뒤 목록에 넣었다.
하지만 이렇게 하니까 예제가 안 풀렸다. 디버깅 하다가, 전부 균등하게 나뉘는 경우에 같은 크기의 조각을 여러 번 나누는 걸 보고 자르는 횟수에 낭비가 있을 것 같았다. 한 번에 묶어서 처리해보려고 n 등분으로 나누게 해봤는데 AC 를 받아서 오히려 찜찜했다.
그래서 왜 n 등분을 해야 맞고, 원래 코드에서 어느 부분이 잘못됐는지 고민해봤다. 결과만 말하자면, 일부만 고려해서 생긴 문제였다. 이등분할 때 가장 가벼운 조각의 무게에 맞춰 자르게 되면 균일하게 나누어야 차이가 최소화된다는 증명에 어긋났고, 이등분만 할 때 균일하게 자르기만 하면 1/2, 1/4, 1/8, ..., 1/(2^n) 만 확인할 수 있어 모든 부분을 고려하지 못했다. 따라서 이와 같은 이유로 균일하게, n 등분으로 자르도록 해야 AC 를 받을 수 있다.
구글링하다가 1088번: 케이크에서 내 문제의 풀이를 찾을 수 있었다.
자세한 유도 과정은 아래에 이미지로 첨부하겠다.
// 00:35 ~ 01:40
// 14:00 ~ 14:55
#include <iostream>
#include <list>
#include <algorithm>
#include <tuple>
using namespace std;
int main(void)
{
int N, M;
double input, min_diff;
tuple<double, double, int> temp, div;
list<tuple<double, double, int>> cake;
list<tuple<double, double, int>>::iterator first, last, pos;
cin >> N;
for (int i = 0; i < N; ++i)
{
cin >> input;
cake.push_back({ input, input, 1 });
}
cake.sort();
first = cake.begin();
last = cake.end();
--last;
min_diff = get<0>(*last) - get<0>(*first);
cin >> M;
while (M--)
{
temp = *last;
--last;
cake.pop_back();
get<0>(temp) = get<1>(temp) / ++get<2>(temp);
pos = upper_bound(cake.begin(), cake.end(), temp);
cake.insert(pos, temp);
first = cake.begin();
last = cake.end();
--last;
min_diff = (min_diff < get<0>(*last) - get<0>(*first)) ? min_diff : get<0>(*last) - get<0>(*first);
}
cout << fixed;
cout.precision(30);
cout << min_diff << '\n';
return 0;
}
// 균일하게 나누지 않아도 된다.
// 하나의 조각을 꼭 2개로 나누는 게 아니라 여러 개로 나눌 수 있다.
느낀 점
지금까지의 그리디 문제는 직관에 의해서만 풀이하고, 따로 자세한 증명과 유도 과정을 거친 적은 없다. 이번 문제를 풀면서 처음으로 증명 비슷한 걸 해봤는데, 다른 분의 증명을 참고하며 틀린 이유를 찾아서 그런지 나름 재미있었다. 혼자 찾으라고 했으면 못 했을 것 같다 ㅋㅋ 그래도 이번 문제를 통해 그리디 문제에 대해 어떻게 접근해야하는지 감이 온 것 같다.
꼭 그리디 문제에 한정하지 않고, 다른 문제에 대해 풀이하더라도 일명 '맞왜틀' 상황 때 증명을 해보면서 놓치는 부분을 확인할수도 있을 것 같다. 열심히 공부해야겠다 ㅠㅠ