USACO 2005 December Bronze- 볼링 점수 > 문제은행 : 정보올림피아드&알고리즘




2711 : 볼링 점수

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
5 회   
시도횟수
20 회   

문제

꿀꿀이 올림피아드에 새로운 종목인 볼링이 추가되었다. 하지만 일반적인 볼링을 할 수 없는 꿀꿀이들은 나름대로의 규칙을 만들었다.


아래 그림과 같이 삼각형 모양의 볼링핀을 세운다.

볼링핀에는 0에서 99까지의 정수가 적혀있다.

맨 위에 행에서 맨 아래 행으로 진행하는데 좌 우 대각선 열로 이동한다.

맨 아래 행까지 오면 그때까지 만난 볼링핀에 적힌 점수의 합으로 스코어를 계산한다.



볼링핀에 대한 정보가 주어질 때 최대 점수는 얼마나 될까?


입력형식

첫 행에 행의 수 N(1 ≤ N ≤ 350)이 주어진다.
이어서 N개의 행에 걸쳐 볼링핀의 점수를 나타내는 정수가 공백으로 구분되어 주어진다.


출력형식

획득할 수 있는 최대 점수를 출력하시오.


입력 예

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

출력 예

30


경기도 안양시 동안구 평촌대로 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