https://www.acmicpc.net/problem/6498
| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
엘리어스 감마 코드는 양의 정수로 이루어진 수열을 인코딩 하는데 사용하는 코드이다. 이 문제에서는 0도 인코딩할 수 있게 변형한 코드를 사용한다.
정수 n을 인코딩하는 과정은 다음과 같다.
1. n의 비트의 개수를 k라고 한다.
2. 0을 k-1개 쓰고, 그 뒤에 1을 쓴다.
3. 그 다음 n을 이진수로 쓴다.
0부터 8까지 숫자를 인코딩한 결과는 아래와 같다.
| 숫자 | 이진수 | 비트의 수 | Prefix | 코드 |
| 0 | 0 | 1 | 1 | 10 |
| 1 | 1 | 1 | 1 | 11 |
| 2 | 10 | 2 | 01 | 0110 |
| 3 | 11 | 2 | 01 | 0111 |
| 4 | 100 | 3 | 001 | 001100 |
| 5 | 101 | 3 | 001 | 001101 |
| 6 | 110 | 3 | 001 | 001110 |
| 7 | 111 | 3 | 001 | 001111 |
| 8 | 1000 | 4 | 0001 | 00011000 |
정수 수열을 인코딩하려면, 수열의 각 숫자를 코드로 변환한 뒤, 수열에서 나온 순서와 동일하게 이어 붙이면 된다.
각각의 인코딩된 코드를 원래 숫자로 디코딩하려면, 이진수 표현 앞에 붙는 k개의 비트는 매우 중요하다. 인코딩된 수열을 읽을 때, 1을 읽기 전에 k-1개의 0을 읽었다면, 다음 k개의 비트가 인코딩된 숫자라는 뜻이다.
인코딩된 정수 수열의 길이를 줄이려면, 다음과 같은 두 가지 최적화를 생각해 볼 수 있다.
1. Prefix가 k비트를 나타내는데, 수열에 비트의 길이가 k인 숫자가 없는 경우가 있다. 이 경우에는, 이 prefix는 k+1비트를 나타내는 것으로 사용할 수 있다. 만약, k+1비트를 나타내는 prefix가 이미 있는 경우에는 k+2비트를 나타내는 prefix로 사용하고, 이와 같은 식으로 계속 한다.
2. 비트의 길이가 k인 모든 숫자의 앞에 0을 붙이면, 그 숫자는 모두 k+1개 비트를 가지게 만들고 첫 번째 최적화를 사용하는 방법도 있다. 이 방법은 k비트 숫자가 매우 적고, k비트 이상 숫자가 많은 경우에 효과적이다.
정수 수열을 인코딩한 결과의 길이를 최소로 하려고 한다. 수열의 숫자가 주어지지 않으며, 수열에서 비트의 개수가 i인 수의 개수를 ci라고 한다.
예를 들어, c1=2, c2=4, c3=0, c4=1인 경우를 생각해보자. (수열 2,1,3,8,0,2,3이 이 경우에 해당한다) 최적화를 하지 않은 엘리어스 감마 코딩의 길이는 2×(1+1) + 4×(2+2) + 0×(3+3) + 1×(4+4) = 28이 된다. 1번 최적화를 사용해 prefix 001을 4비트 숫자를 나타내는 것으로 사용해 1비트를 줄일 수 있다. 또, 최적화 2번을 사용해 1비트 앞에 0을 붙여 2비트로 만들 수 있다. 여기서 다시 최적화 1번을 사용해 prefix 1은 2비트 숫자에 사용하고, prefix 01은 4비트 숫자에 사용하면, 인코딩된 문자열의 길이는 6×(1+2) + 1×(2+4) = 24가 된다.
두 최적화 방법은 여러 번 사용할 수 있다. 두 방법을 적절히 사용해 가능한 길이중 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n이 주어진다. (1 ≤ n ≤ 128) 둘째 줄에는 c1부터 cn까지 값이 주어진다. (0 ≤ ci ≤ 10000) 입력은 n=0으로 끝난다.
출력
각 테스트 케이스 마다 입력으로 주어진 수열의 최소 엘리어스 감마 인코딩 길이를 출력한다.
풀이
문제가 좀 난해합니다. 처음에 이해를 잘못하는 바람에 G4로 레이팅 된 문제를 거의 D3 정도로 바꿔버렸어요. (D3 안해봐서 어느정도인지 모름)
문제에서 말하는 엘리어스 감마 코드는 실제론 반드시 홀수 자리의 코드를 만들어냅니다. 하지만 이 문제에서는 짝수 자리의 코드를 생성하도록 바뀌어있어요. 여러 숫자가 구분자 없이 비트로 나열되어 있다면 어디가 새로운 숫자의 시작인지 알 수 없습니다. 따라서 비트의 길이를 나타내는 0을 숫자 앞에 먼저 배치하고 1이 나오면 그 다음부터 비트의 자리수를 세어보도록 하는 코드입니다. 그러니까 예를 들어 110을 00110로 나타냅니다. 앞에 밑줄친 부분이 1 뒤에 이어질 비트의 길이를 나타내고 있습니다.
문제에서 말하는 최적화는 이와 같은 경우를 말합니다. 표현하고자 하는 숫자가 4개 있다고 해봅시다. [1, 11, 10, 1001]입니다. 이 경우, 대응되는 인코딩 결과는 [11, 0111, 0110, 00011001]입니다. 쭉 나열하면 110111011000011001로 총 18자리가 됩니다.
1001에 부여한 코드가 0001입니다. 그런데 비트 길이가 3인 숫자가 현재 없습니다. 그러니 아깝게 4자리 비트에 0001을 부여하지 말고, 부여하지 못한 하나 짧은 코드인 001을 부여합니다. 그러면 11011101100011001로 17자리, 1자리가 줄어들었습니다. 이게 첫 번째 최적화 방법입니다.
1의 앞에 0을 붙여봅시다. 01이 되어도 나타내는 값은 1과 다르지 않습니다. 하지만 숫자의 비트 길이는 달라졌습니다. 이렇게 비트의 길이를 더 늘려서 뒤에 나오는 다른 길이의 숫자와 같은 코드를 부여할 수 있습니다. 이렇게 하면 또 코드 하나를 아낄 수 있으므로 인코딩 된 전체 코드의 길이를 줄일 수 있습니다. 1을 두 자리로 늘려 01로 관리하면, 2자리 비트 길이의 숫자들에게 01이 아닌 코드 1을 부여할 수 있습니다. 그리고 4자리 비트 길이의 숫자에겐 0001도, 001도 아닌 01을 부여할 수 있습니다. 인코딩 결과는 [101, 111, 110, 011001]입니다. 쭉 나열하면 101111110011001로 총 15자리가 됩니다. 이게 두 번째 최적화 방법입니다.
따라서 문제에서 설명하는 인코딩 방식으로 [1, 11, 10, 1001] → 18자리 코드 → 15자리 코드로 최적화 할 수 있습니다.
여기서 부여하는 코드의 길이를 아끼려고 가장 짧은 코드인 1을 가장 빈도가 많은 비트 길이에 부여하는 것은 안됩니다. 코드는 항상 오름차순으로 부여되는 것이 조건에 맞습니다. 첫 번째 최적화 방법은 비트 길이가 k인 숫자가 없다면 k + 1에게 k의 코드를 넘겨주도록 하고 있기 때문입니다. 만약 이 조건을 무시하고 가장 짧아질 수 있도록 코드를 부여하게 한다면 문제의 난이도가 수직상승합니다...
이제 문제를 이렇게 생각해볼 수 있습니다. 숫자 길이가 i, 그러니까 Ci까지의 값들을 코드 길이 j로 나타낼 수 있는 가장 짧은 인코딩 길이를 dp[i][j]라고 해보고 2차원 배열을 그렸습니다.
dp[i][j]를 구성하려면 Ci에 대해 j만큼의 코드를 부여한 것을 이전 값에 더해주어야 해요. dp[i-1][j]부분을 비워놨는데 그 이유는 dp[i - 1][i]와 같은 경우는 고려할 필요가 없기 때문입니다. dp[i - 1][i]보다 dp[i - 1][i - 1]이 무조건 짧기 때문에 그렇습니다. 그런데 이전에 등장한 Ci-1의 숫자에 0을 덧붙여서 길이를 Ci로 늘려버릴 수 있습니다. 그런 경우를 고려해 점화식을 다음과 같이 세울 수 있습니다.
dp[i][j] = min(dp[k][j - 1] + (sum(C[j], C[j + 1], ..., C[k])) * (i + j)) (단, i ≥ j 그리고 j - 1 ≤ k ≤ i)
# dp[k][j - 1] = 길이가 k인 숫자까지 길이 j - 1의 코드를 사용해 표시한 가장 짧은 인코딩 길이
# sum(C[j], C[j + 1], ..., C[k]) = 비트 길이가 j~k인 숫자의 개수
# i + j = sum(~)을 통해 얻은 모든 숫자는 i + j 길이로 인코딩 됨
굉장히 복잡복잡하네요. 좀 더 직관적인 그림으로 이 점화식을 표현해보자면 이런 식입니다.
노란 구역의 값을 구성하려면 파란 부분의 값을 확인해서 추가되는 길이를 더해보고 가장 짧은 것을 골라내면 됩니다.
마지막으로 숫자 길이 n까지를 모두 확인하면 dp[n][1]부터 dp[n][n]까지의 값 중 가장 작은 값이 가장 짧은 최적 인코딩 결과가 됩니다. 혹시 dp[n][n] 부근의 값이 구성되지 않을 경우를 대비해 dp테이블의 값은 초기 값은 아주 큰 값으로 정해주는 것이 좋습니다.
덧붙여서 점화식이 커누스 최적화를 적용할 수 있는 형태입니다. 적용하면 훨씬 빨라집니다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
inf = int(1e9)
while True:
n = int(input())
if n == 0: break
dp = [[inf] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0
c = [0] + list(map(int, input().split()))
s = [0] * (n + 1)
for i in range(1, n + 1):
s[i] = s[i - 1] + c[i]
for j in range(1, n + 1):
for i in range(j, n + 1):
for k in range(j - 1, i):
t = dp[k][j - 1] + (s[i] - s[k]) * (i + j)
if dp[i][j] > t:
dp[i][j] = t
res = dp[n][1]
for j in range(2, n + 1):
if res > dp[n][j]:
res = dp[n][j]
print(res)
solution()
# Knuth's Opt
import sys
input = sys.stdin.readline
def solution():
inf = int(1e9)
while True:
n = int(input())
if n == 0: break
dp = [[inf] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0
c = [0] + list(map(int, input().split()))
s = [0] * (n + 1)
for i in range(1, n + 1):
s[i] = s[i - 1] + c[i]
opt = [[0] * (n + 1) for _ in range(n + 1)]
for j in range(1, n + 1):
opt[n][j] = n # 경계 처리
for i in range(n, j - 1, -1):
l = opt[i][j - 1]
r = opt[i + 1][j] if i + 1 <= n else n
dp[i][j] = inf
for k in range(l, r + 1):
t = dp[k][j - 1] + (s[i] - s[k]) * (i + j)
if dp[i][j] > t:
dp[i][j] = t
opt[i][j] = k
res = dp[n][1]
for j in range(2, n + 1):
if res > dp[n][j]:
res = dp[n][j]
print(res)
solution()
