Informatica Online Judge

  3 by n Tiling Game #1 [1531 / 05FB]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 27   Total Tried : 77


The Champion of this Problem (C++) : gs17040 - 0ms / 1414byte
My Best Submission (C++) : N/A

[JKJeong 2016]

Background

3 x n 격자판이 있다.

앞의 문제들과 마찬가지로 이 판을 1x2(회전가능) 빈 칸 없이 도미노들로 채우고자 한다.

단 이 판에는 점수들이 쓰여있다.

하나의 타일을 채울 때 얻는 점수는 그 타일이 덮는 칸에 적힌 수들 중 작은 값이다.

만약 하나의 도미노로 3, 2로 쓰여진 연속된 칸을 덮었다면 이 때 얻는 점수는 min(3, 2)이므로 2점이다.

점수가 적힌 격자판이 주어질 때, 규칙을 지키면서 모두 타일을 채울 때 얻는 최고점수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n이 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 20
각 칸에 적히는 수는 1000이하의 자연수이다.

Output

규칙을 지키면서 채울 때 얻는 최고점수를 출력한다.
단, 타일을 채우는 것이 불가능하면 "0"을 출력한다.

IO Example

입력
2
1 2
3 4
0 0

출력
4

가로로 3개를 놓으면 min(1, 2) + min(3, 4) + min(0, 0) = 4 이보다 더 많은 점수를 얻을 수는 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]