N=10, K=2인 경우
5층부터 낙하시킬 경우 바이너리 서치를 하면 최악의 경우엔 6회가 필요한데,
4층부터 낙하시킬 경우,
-> 금고가 4층에서 깨질 경우 1~3층 순회 (총 4회, 4->1->2->3)
-> 금고가 4층에서 깨지지 않을 경우 7층에서 실험, 여기서 깨질 경우 5~6 순회(총 4회, 4->7->5->6)
-> 7층에서도 깨지지 않았을 경우 9층에서 실험, 여기서 깨질 경우 8층만 확인(총 4회, 4->7->9->8)
-> 9층에서도 깨지지 않았을 경우 10층만 확인, 총 4회, 4->7->9->10
로 4회의 낙하 실험이면 충분합니다.
ckdgus2482 7년 전
일단 문제에 약간 오류가 있어보이는게 N층에서 부숴지지 않을 수도 있다고 했는데 그런 경우면 1~N층 사이에 F층이 존재하지 않는거잖아요.
그러면 E(N, K)의 정의를 F층이 존재하는지 존재한다면 몇 번째 층인지 찾는데 필요한 최소 낙하횟수로 바꿔야할것 같습니다.
그리고 제가 푼 방법은 이분탐색의 변형입니다. 문제에서 F층이 몇번째 층이더라도 찾아낼 수 있는 최소 낙하횟수라고 하였으므로 이분탐색을 하되 항상 최악의 경우만 발생하는걸로 생각하였습니다. 그래서 주어진 범위 내에서 가운데의 층에서 낙하를 하는데 이때는 항상 금고가 깨지는걸로 생각했구요. 그러면 낙하 횟수는 1 + f(n/2, k-1)이 될 것입니다. 다만 기저사례로서 k==1인 케이스를 잡았는데 금고가 한개밖에 없으면 어쩔 수 없이 순차 탐색을 해야하기 때문입니다. 이때도 마찬가지로 최악의 경우를 상정해야하므로 주어진 범위 내의 모든 층을 확인해봐야하는 경우(주어진 범위 내에 F층이 없는 경우거나 가장 마지막 층이 F층인 경우)로서 n을 반환하게 했습니다.
답이 틀리다고 하는데 제 알고리즘에 어떤 오류가 있는지 알려주실분 계신가요?