시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
3.0 초 512 MB 811 436 (54%) 385
문제
주어지는 숫자 삼각형에서, 수의 합이 최대가 되도록 하는 프로그램을 작성하여라. 이 때, 수의 합은 가장 윗쪽의 숫자에서 출발하여 왼쪽 아래 혹은 오른쪽 아래로 이동하며 지나가는 모든 수들을 더한 것이다. ``` 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ``` 위의 숫자 삼각형에서 합이 최대가 되는 방법은 $7, 3, 8, 7, 5$를 순서대로 이동하는 방법이다.
입력
첫 번째 줄에 삼각형의 세로 크기 $N$이 주어진다. ($N$은 $5,000$이하의 자연수이다.) 두 번째 줄부터 $N$개의 줄에 걸쳐 숫자 삼각형이 주어진다. 숫자 삼각형의 $i$번째 줄은 $i$개의 숫자로 이루어지는데, 각 숫자는 $0$ 이상 $100$ 이하이다.
출력
첫 번째 줄에 숫자 삼각형에서 만들 수 있는 수의 합의 최대값을 출력한다.
힌트
#### 입력 예제 ``` 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ``` #### 출력 예제 ``` 30 ```