RSS Feed

기울어진 비용 코딩

Problem 219

출제 일시 : 2020-10-10 00:01:04

AB는 0과 1로 이루어진 비트 문자열입니다.
만일 B왼쪽 length(A) 길이의 비트와 A가 같다면, AB접두사라고 합니다.
예를 들어, 00110은 001101001의 접두사지만 00111나 100110의 접두사는 아닙니다.

크기 n접두사 없는 코드는 어떤 문자열도 서로 다른 문자열의 접두사가 되지 않는 n개의 서로 다른 비트 문자열 모음입니다. 예를 들어, 다음은 크기 6의 접두사 없는 코드 예입니다:

0000, 0001, 001, 01, 10, 11

0을 전송하는 데 1원이 들고, 1을 전송하는 데는 4원이 든다고 가정해 봅시다.
그러면 위의 접두사 없는 코드를 모두 전송하는 데는 35원이 드는데 이 값은 이 문제에서 질문하는 기울어진 가격체계의 최소 비용입니다.
짧게, Cost(6) = 35라고 씁니다.

Cost(109)는 얼마입니까?


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