BOJ 2266 금고 테스트

N층짜리 빌딩이 있다. F층은 금고가 부서지는 최소 층이다. 즉 F층 이상의 층에서 금고를 떨어뜨리면 금고는 부서지고 F층 아래에서는 떨어뜨려도 부서지지 않는다. F층을 알아내기 위해 금고 k개를 가지고 떨어뜨려 보려고 하는데, 금고가 부서지면 다시 사용할 수 없다. F층이 몇층이든 간에 N층짜리 빌딩에서 k개의 금고를 이용해 F층을 알아낼 수 있는 금고의 낙하 횟수의 최소값을 구하는 문제이다.

구하라고 하는 것이 잘 와닿지가 않는다. 어렵다.

금고가 1개일 경우, 그 금고가 F층을 찾기 전에 깨지면 더 이상 F층을 알 방법이 없으므로 이 경우에는 1층부터 한 층씩 올라가면서 테스트를 해봐야 해서 금고의 낙하 횟수의 최소값은 N이 된다. 이 예에서 알 수 있듯이 우리가 구하고자 하는 것은 F가 몇층이든 간에 N층자리 빌딩에서 k개의 금고를 이용해 F층을 알아낼 수 있는 금고의 낙하 횟수의 최소값이다. 여기서 최소값이긴 한데 (F가 몇 층이든 간에)라는 조건이 있기 때문에, 결국 F가 1층부터 N층일 수 있는 것이고 F가 1부터 N 층일 때의 각각에 대한 최소값을 구해서 그 중 최악의 경우(최대값, F가 몇 층이든 간에 라는 조건이 있으므로!)을 구해야 하는 문제이다.

그럼 F를 1층, 2층, ...N층이라 가정하고 k개의 금고를 최소 몇 번 떨어뜨려야 F를 알아낼 수 있는지 구해보면 될 것이다.

어떻게 할까? 쉽게 생각할 수 있는 것은 만약 금고를 떨어뜨려 보다가 금고가 하나가 남는다면 한 층 한 층 아래서부터 차례로 봐야할 것이다. 그러면 금고가 하나 남기 전까지는 뭘 해야할까? 바로 F층이 존재하는 범위가 처음에는 1~N이었다면, 금고를 1~N중간에 떨어뜨려서 범위를 반으로 줄일 수 있을 것이다(이분 탐색처럼) 이렇게 하나가 남을 때까지 범위를 줄이고 하나가 남으면 최종적으로 줄여진 범위내에서 가장 아래부터 하나씩 보는 것이다.

이분 탐색을 할 때 주의할 점이 안 깨지는 경우 재활용 가능하다는 것과, mid에서 깨지는 경우 r=mid-1로 아래층으로 하는 게 아니라 자기 자신(mid)도 F층일 가능성이 있으므로 r=mid로 해줘야 한다. 그리고 l==r이 되면 이분 탐색만으로 F층을 구한 것이 된다.

WA를 받았다. 질문 게시판을 봤는데, portableangel님의 멋진 답변이 있었다.
왜 이분탐색으로 풀면 안 되는지를 직접 예를 들어 설명해 주셨다.


그리고 이분 탐색으로 구현하면서 최악의 경우를 구하는 것이었다면 나처럼 복잡하게 할 필요 없는 것 같다... 좀 완전히 잘못 생각한 것 같다.


백준님이 dp로 설명해 주셨는데, dp를 조금 고민해보다가 풀이를 봐야겠다.
portableangel님의 답변에 기반하여 생각해 보면 꼭 가운데 층에서 떨어뜨리는 게 좋은 것은 아니기 때문에 1층부터 n층까지 다 떨어뜨려 보는 경우를 해봐야할 것 같다.
d[n][k] = n층에서 k개의 금고를 가지고 F층을 알아낼 수 있는 최소의 금고 낙하 횟수

d[n][k] = MIN(s층에서 시작, MAX(깨진 경우:d[s-1][k-1], 깨지지 않은 경우:d[n-s][k]) )
떨어뜨리는 것을 모든 층에서 다 해봐야하고 그 중 최대(최악)의 경우를 구해서 그것들 중 최소를 구하면 될 것이다.
여기서 깨진 경우 d[s-1][k-1]에서 좀 헷갈렸는데, s에서 깨졌다면 s개가 아니라 s-1개만 보면 되는 이유는 s번째는 이미 봤고 깨졌다는 걸 알기 때문에 s-1개를 본 결과에 따라 s번째를 판단할 수 있기 때문이다.**

와 AC를 받았다... 백준님의 설명을 저번 주에 듣긴했지만 기억이 안났었는데, 나도 모르게 기억하고 있었던 건가... portableangel님의 설명이 많이 도움이 됐다.

그리고 시간이 많이 나와서 다른 분들 코드를 보는데, sys7961님의 코드가 나랑 비슷한데, 시간은 많이 차이가 나서 자세히 보니 나는 dp(n, k)를 호출한 반면에,
sys7961님은 dp(n, min(9, k))를 호출하셨다. 아까 이분탐색으로 짰던 코드에서 n을 500으로 하고 해보면 보통 9가 나오던데 아마 500층 이내에서는 9개가 넘는 금고는 불필요한 것 같아보인다. 9개의 금고로도 커버가 되는 것 같다. sys7961님도 대단하신 것 같다. 난 아까 9가 나오는 걸보고도 생각도 못했는데...

이 문제는 예전에 면접이나 코딩 테스트에서도 자주 나왔던 문제라고 하고 유명하다고 한다. 수학적으로 접근하는 방법도 있고.. 그리고 좀 푸는데 애먹었으니 나중에 꼭 다시 혼자 힘으로 풀어보도록 하자.