소들의 파친코

면접 대비

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

요약

R개의 행으로 이루어진 삼각형 모양의 못 점수가 주어질 때, 맨 위 못에서 시작해 각 단계마다 바로 아래 두 못 중 하나로 내려가며 마지막 행까지 도달하는 경로의 최대 합을 구한다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 배열, 행렬, 재귀
정답자: 아직 제출이 없습니다

문제

소들이 파친코라는 게임을 하고 있습니다. 위에서 공을 떨어뜨리면 아래로 내려가면서 못에 부딪히고, 좌우로 조금씩 방향을 틀며 맨 아래로 나옵니다.

이 파친코는 특별합니다. 공은 항상 $R$ 개의 못 줄 중 맨 위 못에 먼저 부딪힙니다 ( $1 \le R \le 25$ ). 그다음에는 바로 아래의 왼쪽 또는 오른쪽 못에 부딪힙니다. 여기서 다시 바로 아래의 왼쪽 또는 오른쪽 못으로 내려가며, 이 과정을 맨 아래 줄까지 반복합니다. 공은 방금 부딪힌 못에서 너무 멀리(못 반 칸을 넘게) 벗어나지 않습니다.

이 게임의 점수 계산도 독특합니다. 내려오는 길에 부딪히는 못마다 점수 $X_{ij}$ ( $0 \le X_{ij} \le 3000$ )를 얻습니다. 소들은 이 기계에서 점수를 최대로 만들고 싶어 합니다. 얻을 수 있는 가장 높은 점수는 얼마일까요?

다음은 삼각형과 좋은 경로의 예시입니다. 별표(*)로 표시된 못들이 공이 지나가는 경로입니다.

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

위 예시에서 $7 \to 3 \to 8 \to 7 \to 5$ 경로가 합 $30$ 으로 가장 높습니다. $7$ 에서 $8$ 로, 다시 $8$ 로 가는 것은 불가능합니다. 셋째 줄의 $8$ 은 너무 멀리 떨어져 있기 때문입니다.

입력

첫째 줄: 정수 $R$ .
둘째 줄부터 $R+1$ 째 줄까지: $i+1$ 째 줄에는 기계의 $i$ 번째 줄 점수 $X_{i1}, X_{i2}, \dots, X_{ii}$ 가 공백으로 구분되어 주어집니다( $i$ 개의 정수).

출력

첫째 줄: 얻을 수 있는 최대 점수를 나타내는 정수 하나.

예제3

예제 1
입력
```
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
```
예상 출력
```
30
```
예제 2
입력
```
1
42
```
예상 출력
```
42
```
예제 3
입력
```
3
7
3 8
8 1 0
```
예상 출력
```
18
```