3246 - 삼각형 수

• Submit
• Status
• Discuss
• Summary

Description

아래의 삼각형 모양의 표에 적당한 숫자들이 적혀했다.

위의 그림은 크기가 3인 표에 숫자가 적혀있는 모습을 나타내고 있다.

우리는 여기서 총 13개의 삼각형을 찾을 수 있다 (크기가 1인 삼각형 9개, 크기가 2인 삼각형 3개, 크기가 3인 삼각형 1개) 크기가 4 이하인 삼각형 모양의 표에서 존재하는 삼각형들의 개수는 아래와 같다.

 

# of Rows:	N = 1	N = 2	N = 3	N = 4
# of Sub-triangles:	1	5	13	27

이런 각 삼각형마다 삼각형에 적힌 숫자들의 합을 구할 수 있을 것이다. 삼각형 모양의 표가 주어졌을 때, 그 안에서 찾을 수 있는 삼각형들에 대해, 안에 있는 값들의 합 중 최대값을 찾아 출력해보자.

 

Input

입력은 여러 테스트케이스로 이루어져 있다.

각 테스트케이스마다 첫번째 수는 삼각형의 크기를 나타내는 숫자 n이 주어진다. (0 < n ≤ 400) 그 다음 n^2 개의 수에 걸쳐 삼각형 표에 들어가있는 수들이 주어진다. 순서는 위에서 아래 순이며, 높이가 같은 경우 왼쪽에서 오른쪽 순서대로 수가 주어진다. 표에 들어가는 수의 절대값은 1000을 넘지 않는다.

n으로 0이 들어오는 경우 입력을 종료한다.

Output

각 테스트케이스에 대해서 아래와같은 정보를 출력한다.

k. D

k는 테스트케이스의 번호이고(1부터 시작.) D는 문제에서 요구하는 정답이다.

Sample Input

3 6 -24 0 12 -10 12 40 -4 6
4 1 1 -1 1 1 -1 1 -1 1 1 -1 1 -1 1 -1 1
0

Sample Output

1. 54
2. 4

Source

Regionals 2008, Africa/Middle East - Arab and North Africa