KOI 두부 공장에서 만들어내는 크기가 N (N <= 11) 인 두부모판이 있다.
이 모판을 크기의 단위두부가 2개 붙어있는 형태의 포장단위(즉, 1*2 혹은 2*1 크기)로 잘라서 판매한다. 그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 잘려진 포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 그림 1과 같이 정해진다.
포장단위에 있는 두 단위두부가 [A,A]급이면 100원을 받고, [A,B]급이면 70원을, [A,C]급이면 40원을, [B,B]급이면 50원을, [B,C]급이면 30원을, [C,C]급이면 20원을 받는다.
포장단위에 있는 두 개의 단위두부 중 하나라도 F급이 있으면 이 포장단위는 한푼도 받을 수 없다. N*N 두부 모판의 품질이 주어질 때, 가장 높은 가격을 받도록 두부 모판을 혹은 크기의 포장단위들로 자르고자 한다. 예를 들어 그림 2와 같은 3*3 두부 모판이 주어져 있다고 하자.
이 경우, 그림 3과 같이 자르면 4개의 포장단위가 만들어진다.
이때, 이들 포장단위의 가격은 [A,A]=100, [F,C]=0, [A,C]=40, 그리고 [A,B]=70 이다. 여기서 오른쪽 위 [C]와 같이 단위두부 하나는 포장단위가 아니므로 판매할 수 없다. 따라서 총 가격은 210원이 된다. 이 가격은 그림 2와 같은 3*3 두부모판에서 받을 수 있는 가장 높은 가격이다.
두부모판의 크기와 단위두부의 등급이 주어질 때, 이를 포장단위로 잘라 받을 수 있는 총 가격의 최대값을 구하는 프로그램을 작성하시오.
입력 3 AAC FCA ACB 출력 210
출처:제23회한국정보올림피아드(2006.7.14) 고등부 문제 2