KOI 전국 2006 고2- 두부 모판 자르기 > 문제은행 : 정보올림피아드&알고리즘

1993 : 두부 모판 자르기

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
38 회   
시도횟수
82 회   

문제

KOI 두부 공장에서 만들어내는 크기가 NxN(N≤11)인 두부 모판이 있다. 

 

이 모판을 1x1 크기의 단위두부가 2개 붙어있는 형태의 포장단위(즉, 1x2 혹은 2x1 크기)로 잘라서 판매한다. 

그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 

잘려진 포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 그림 1과 같이 정해진다.

 

 

 

포장단위에 있는 두 단위두부가 [A,A]급이면 100원을 받고, [A,B]급이면 70원을, [A,C]급이면 40원을, [B,B]급이면 50원을, [B,C]급이면 30원을, [C,C]급이면 20원을 받는다. 

 

포장단위에 있는 두 개의 단위두부 중 하나라도 F급이 있으면 이 포장단위는 한푼도 받을 수 없다. 

 

NxN 두부 모판의 품질이 주어질 때, 가장 높은 가격을 받도록 두부 모판을 1x2 혹은 2x1 크기의 포장단위들로 자르고자 한다. 

 

예를 들어 그림 2와 같은 3x3 두부 모판이 주어져 있다고 하자.

 

 

 

이 경우, 그림 3과 같이 자르면 4개의 포장단위가 만들어진다.

 

 

 

이때, 이들 포장단위의 가격은 [A,A]=100, [F,C]=0, [A,C]=40, 그리고 [A,B]=70 이다. 

여기서 오른쪽 위 [C]와 같이 단위두부 하나는 포장단위가 아니므로 판매할 수 없다. 따라서 총 가격은 210원이 된다.

이 가격은 그림 2와 같은 3x3 두부모판에서 받을 수 있는 가장 높은 가격이다.

 

두부모판의 크기와 단위두부의 등급이 주어질 때, 이를 포장단위로 잘라 받을 수 있는 총 가격의 최댓값을 구하는 프로그램을 작성하시오. 부분 점수는 없다.

 

 


입력형식

첫째 줄에는 두부모판의 크기를 나타내는 N(2≤N≤11) 이 주어진다.

둘째 줄부터 N 줄에 걸쳐 각 줄에 두부모판의 단위두부의 등급들이 행단위로 등급사이에 공백 없이 첫 번째 행부터 차례로 주어진다.


출력형식

입력된 두부모판을 포장단위로 잘라서 받을 수 있는 최대 가격을 첫째 줄에 출력한다.

입력 예

3
AAC
FCA
ACB

출력 예

210


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP