RSS Feed

최소 비용 검색

Problem 328

출제 일시 : 2021-01-27 00:25:17

정수 집합 {1, 2, ..., n}의 수 하나를 숨기고 질문을 통해 알아내고자 합니다. 어떤 수 하나를 질문하는데는 질문하는 수만큼의 비용이 소요되고, 들을 수 있는 답은 다음 세 가지 중 하나입니다:

  • "추측한 수는 숨겨진 수보다 작습니다", 또는
  • "예, 맞췄습니다!", 또는
  • "추측한 수는 숨겨진 수보다 큽니다".

n이 주어졌을 때, 최악의 경우에 드는 총 비용(즉, 모든 질문에 사용된 수의 합)을 최소화하는 것이 최적 전략입니다.

예를 들어, n=3이라면, 질문할 수 있는 최선은 명백하게 "2"입니다. 답을 들으면 숨겨진 수가 무엇인지 즉시 알 수 있습니다(총 비용 = 2).

만일 n=8이라면, "이진 탐색"형태의 전략을 사용해야 할 것입니다: 첫 질문이 "4"고 숨겨진 수가 4보다 크다면 한 두 번의 추가적인 질문이 필요합니다.
다음 질문이 "6"이라고 합시다. 만일 숨겨진 수가 6보다 크다면, 7인지 8인지 알기 위해서는 세 번째 질문을 해야 합니다.
그러므로, 세 번째 질문은 "7"이 되고 이 최악의 경우에 사용된 총 비용은 4+6+7=17입니다.

n=8인 경우, 첫 질문으로 "5"를 선택하면 최악의 경우에 드는 비용을 상당히 줄일 수 있습니다.
만일 숨겨진 수가 5보다 크다는 답을 들으면, 다음 질문은 "7"이 되고, 숨겨진 수가 무엇인지 확실히 알게 됩니다(총 비용은 5+7=12입니다).
만일 숨겨진 수가 5보다 작다는 답을 들으면, 다음 질문은 "3"이고, 숨겨진 수가 3보다 작다면, 세 번째 질문은 "1"이며, 총 비용은 5+3+1=9입니다.
12>9이므로, 이 전략은 최악의 경우 비용이 12입니다. 이는 이전의 "이진 탐색" 전략에서 얻은 것보다 훨씬 좋은 값입니다; 또한 다른 어떤 전략도 이보다 더 좋을 수는 없습니다.
사실, 이는 n=8인 경우의 최적 전략입니다.

C(n)을 n에 대한 최적 전략을 사용했을 때 최악의 경우 비용이라 하면,
C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12입니다.
유사하게, C(100) = 400 이고 $\sum \limits_{n = 1}^{100} {C(n)} = 17575$입니다.

$\sum \limits_{n = 1}^{200000} {C(n)}$ 값을 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.