시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 499 | 81 | 45 | 22.613% |
상근이는 팩스 이미지를 압축하는 계획을 만들려고 한다. 스캐너를 통해서 이미지를 입력받으면, 1과 256사이의 정수로 이루어진 수열로 변환된다. 예를 들어, 아래와 같은 수열로 이미지를 변환할 수 있다.
1, 1, 1, 1, 1, 46, 1, 1, 1,1, 1, 1, 2, 1, 2, 1, 1, 25, 26, 25, 25, 255, 256, 256, 256, 255,...
이미지를 반드시 정확하게 변환할 필요는 없다. 따라서, 상근이는 수열의 각 정수를 레벨 4개(1, 86, 172, 256)으로 나타내려고 한다. 그리고, 이 레벨은 다음과 같이 2-bit 코드로 나타낼 수 있다.
Level | 1 | 86 | 172 | 256 |
---|---|---|---|---|
Code | 00 | 01 | 10 | 11 |
그림 안에는 같은 색으로 이루어진 영역(예를 들면 공백)이 있다. 이 영역을 변환하면 유사한 정수가 연속해서 나타난다. 이를 처리하기 위해서 다음과 같은 압축 방법을 사용하려고 한다.
상근이는 작은 양의 에러를 크게 신경쓰지 않기 때문에, 작은 양의 에러는 무시한다. 예를 들어, 입력된 수열이 2, 2, 2, 2, 2, 46, 2, 2 라고 했을 때, 이를 1, 1, 1, 1, 1, 86, 1, 1로 나타낸 다음 변환하면 0000001011000가 되고 전체 에러는 1+1+1+1+1+40+1+1=47 이 된다. 하지만 1, 1, 1, 1, 1, 1, 1, 1 로 나타낸 후 변환하면 전체 에러는 1+1+1+1+1+45+1+1=52가 되어 커지지만 코드가 000000000가 되어 더 짧아진다.
상근이는 변환 비용을 최소로 하는 방법을 찾으려고 한다. 변환 비용은 전체 에러 + W × (변환 코드의 길이)로 계산할 수 있다.
수열이 2, 2, 2, 2, 2, 46, 2, 2 이고, W가 100인 경우에 y1,..., y8 = 1, 1, 1, 1, 1, 86, 1, 1 로 변환하면 코드는 0000001011000이 되고, 변환 비용은 47 + 100 × 13 = 1347이다. 하지만 y1,..., y8 = 1, 1, 1, 1, 1, 1, 1, 1로 변환하면 코드는 000000000이고 변환 비용은 52 + 100 × 9 = 952이다.
첫째 줄에 수열의 길이 N(1 ≤ N ≤ 50), 가중치 W(0 ≤ W ≤ 100)가 주어진다. 다음 N개의 줄에는 수열을 이루는 정수가 차례로 주어진다.
첫줄에는 최소 변환 비용을 출력한다. 그리고 두 번째 줄에는 변환코드를 출력한다.
8 100 2 2 2 2 2 46 2 2
952 000000000