2341번 - 팩스 문제 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 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 |
그림 안에는 같은 색으로 이루어진 영역(예를 들면 공백)이 있다. 이 영역을 변환하면 유사한 정수가 연속해서 나타난다. 이를 처리하기 위해서 다음과 같은 압축 방법을 사용하려고 한다.
- 수열의 첫 번째 수는 위의 표에 나온 2bit 코드로 변환한다.
- 그 다음에 나오는 다른 모든 수에 대해서는
- 만약 수열의 바로 앞에 있는 수가 같은 수라면 0으로 변환한다.
- 앞에 있는 수와 다른 수라면 1을 앞에 붙인 뒤 위 표의 2bit 코드로 변환한다.
상근이는 작은 양의 에러를 크게 신경쓰지 않기 때문에, 작은 양의 에러는 무시한다. 예를 들어, 입력된 수열이 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 × (변환 코드의 길이)로 계산할 수 있다.
- W는 에러와 코드의 길이 중 어느 것을 중요시 하느냐에 따라 입력으로 주어진다.
- 이때 전체 에러는 입력 수열 x1, x2, , xN , 변환 수열 y1, y2, , yN에 대해서 다음과 같다. Σ|xi-yi|
수열이 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개의 줄에는 수열을 이루는 정수가 차례로 주어진다.
출력
첫줄에는 최소 변환 비용을 출력한다. 그리고 두 번째 줄에는 변환코드를 출력한다.
예제 입력 1
8 100 2 2 2 2 2 46 2 2
예제 출력 1
952 000000000
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호