피보나치 압축
시간 제한1초메모리 제한512 MB
정수 기호로 이루어진 문자열이 주어질 때, 빈도에 따라 피보나치 부호를 배정하고 각 접두사의 압축된 비트 길이를 출력한다.
문제
피보나치 압축은 피보나치 수를 바탕으로 한 새로운 종류의 오류 감내 압축이다. 부호는 코드워드의 끝이 아닌 곳에서 연속한 두 개의 “1” 비트가 나타나지 않아야 하고, 끝에서는 두 개의 “1” 비트가 반드시 나타나야 한다는 규칙에 따라 만들어진다. 실제로 이는 i ≥ 2인 각 압축 부호 비트 길이 i마다 그 길이의 압축 부호가 Fibonacci(i − 1)개 존재한다는 뜻이다.
예를 들어 가장 짧은 14개의 피보나치 코드워드는 다음과 같다.
11 011 0011 1011
00011 10011 01011 000011
100011 010011 001011 101011
0000011 1000011 ...
피보나치 압축으로 문자열을 압축할 때는 가장 자주 등장하는 문자에 가장 짧은 부호를 부여한다. 이러한 문자열 s가 주어질 때, 이 체계에 따라 최대한 작게 압축했을 때의 각 접두사의 길이를 구하라.
입력
- 압축할 문자열의 길이 n이 한 줄에 주어진다. (1 ≤ n ≤ 105)
- 문자열 s가 n개의 정수 si의 나열로 한 줄에 주어진다. (0 ≤ si ≤ 106)
출력
|s|개의 줄을 출력한다. i번째 줄은 s의 앞 i개 문자를 압축한 길이를 비트 단위로 나타낸다.