cho.sh두부 장수 장홍준
시간 제한2초메모리 제한128 MB문제 설명
예제1
문제
장홍준은 세로 N, 가로 M 크기의 두부판을 2 x 1 크기의 조각으로 잘라 판다. 각 칸에는 A, B, C, D, F 중 하나의 등급이 적혀 있으며, 두 칸을 붙여 만든 한 조각의 가격은 두 등급의 조합으로 정해진다.
가격표는 다음과 같다.
| A | B | C | D | F | |
|---|---|---|---|---|---|
| A | 10 | 8 | 7 | 5 | 1 |
| B | 8 | 6 | 4 | 3 | 1 |
| C | 7 | 4 | 3 | 2 | 1 |
| D | 5 | 3 | 2 | 2 | 1 |
| F | 1 | 1 | 1 | 1 | 0 |
두 등급의 순서는 가격에 영향을 주지 않는다. 두부판에서 겹치지 않는 2 x 1 조각을 가로 또는 세로로 잘라낼 수 있고, 조각에 포함되지 않는 한 칸짜리 두부는 가격이 0이므로 버린다. 전체 가격 합의 최댓값을 구하시오.
입력
첫째 줄에 두부판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 1 이상 14 이하의 정수이다.
다음 N개의 줄에는 각 줄마다 M개의 문자가 주어진다. 각 문자는 해당 칸의 등급을 나타내며 A, B, C, D, F 중 하나이다.
출력
잘라낸 두부 조각들의 가격 합으로 만들 수 있는 최댓값을 출력한다.
Loading...