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 |