두부 모판 자르기 > 문제은행

본문 바로가기


알고리즘 다이나믹2

1993 : 두부 모판 자르기

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 211 회    시도횟수: 495 회   



KOI 두부 공장에서 만들어내는 크기가 NxN(N≤11)인 두부 모판이 있다. 이 모판을 1x1 크기의 단위두부가 2개 붙어있는 형태의 포장단위(즉, 1x2 혹은 2x1 크기)로 잘라서 판매한다. 그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 잘려진 포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 그림 1과 같이 정해진다.

 

75aaf69980fa1f33c5b54a688ed39a00_1450934 

 

포장단위에 있는 두 단위두부가 [A,A]급이면 100원을 받고, [A,B]급이면 70원을, [A,C]급이면 40원을, [B,B]급이면 50원을, [B,C]급이면 30원을, [C,C]급이면 20원을 받는다. 포장단위에 있는 두 개의 단위두부 중 하나라도 F급이 있으면 이 포장단위는 한푼도 받을 수 없다. NxN 두부 모판의 품질이 주어질 때, 가장 높은 가격을 받도록 두부 모판을 1x2 혹은 2x1 크기의 포장단위들로 자르고자 한다. 예를 들어 그림 2와 같은 3x3 두부 모판이 주어져 있다고 하자.

 

75aaf69980fa1f33c5b54a688ed39a00_1450934 

 

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

 

75aaf69980fa1f33c5b54a688ed39a00_1450934 

 

이때, 이들 포장단위의 가격은 [A,A]=100, [F,C]=0, [A,C]=40, 그리고 [A,B]=70 이다. 여기서 오른쪽 위 [C]와 같이 단위두부 하나는 포장단위가 아니므로 판매할 수 없다. 따라서 총 가격은 210원이 된다. 이 가격은 그림 2와 같은 3x3 두부모판에서 받을 수 있는 가장 높은 가격이다.

 

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


첫째 줄에는 두부모판의 크기를 나타내는 N(2≤N≤11) 이 주어진다.
둘째 줄부터 N 줄에 걸쳐 각 줄에 두부모판의 단위두부의 등급들이 행단위로 등급사이에 공백 없이 첫 번째 행부터 차례로 주어진다.


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

[Copy]
3
AAC
FCA
ACB
[Copy]
210





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.