공 쌓기

면접 대비

시간 제한1초메모리 제한128 MB

요약

삼각형으로 쌓인 공을 고를 때 각 공은 위에 얹힌 두 공을 먼저 골라야 하며, 중간에 멈출 수 있을 때 얻을 수 있는 최대 점수를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 구현, 수학
정답자: 아직 제출이 없습니다

문제

KDK 방송국이 새 게임 쇼를 만들었다. 참가자는 몇 번의 선택을 하고, 그 선택에 따라 상품을 받는다.

공들이 삼각형 모양으로 쌓여 있고, 각 공에는 정수 하나가 적혀 있다. 맨 위 행에는 공이 $1$ 개, 그 아래 행에는 $2$ 개, 이런 식으로 $i$ 번째 행에는 공이 $i$ 개 있다. $i$ 행 $j$ 열의 공은 바로 아래 두 공 위에 얹혀 있으며, 그 공 위에 얹혀 있는 것은 $(i-1)$ 행의 공 (최대 두 개), 즉 $(i-1,\ j-1)$ 과 $(i-1,\ j)$ 이다.

참가자는 공을 하나씩 고를 수 있고, 고른 공에 적힌 수의 합이 점수가 된다. 공을 고르면 그 공은 삼각형에서 제거된다. 점수가 높을수록 더 좋은 상품을 받는다. 단, 어떤 공은 그 위에 얹혀 있는 공을 모두 이미 고른 경우에만 고를 수 있다. 맨 위 공 $(1,\ 1)$ 은 위에 얹힌 공이 없으므로 언제든 먼저 고를 수 있다. 참가자는 매 순간 공을 더 고를지 멈출지 선택할 수 있으며, 공을 하나도 고르지 않으면 점수는 $0$ 이다.

프로그램 PD 김동규는 참가자가 얻을 수 있는 점수의 최댓값이 궁금하다. 그 최댓값은 얼마일까?

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 공이 쌓인 행의 수 $N$ 이 주어진다. ( $1 \le N \le 1000$ ) 이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 정수 $B_{i1},\ B_{i2},\ \dots,\ B_{ii}$ 가 공백으로 구분되어 주어진다. ( $-10^5 \le B_{ij} \le 10^5$ , $1 \le j \le i \le N$ ) $B_{ij}$ 는 $i$ 행 $j$ 열의 공에 적힌 정수이다. (첫 행이 가장 위 행이고, 각 행의 첫 번째 공이 가장 왼쪽 공이다.)

입력의 마지막 줄에는 $0$ 하나가 주어지며, 이는 입력의 끝을 뜻한다.

출력

각 테스트 케이스마다 참가자가 얻을 수 있는 점수의 최댓값을 한 줄에 하나씩 출력한다.

예제4

예제 1

입력

예상 출력

7
0
6

예제 2
입력
```
1
5
0
```
예상 출력
```
5
```
예제 3
입력
```
1
-7
0
```
예상 출력
```
0
```
예제 4
입력
```
3
1
2 3
4 5 6
0
```
예상 출력
```
21
```