본문 바로가기

PKU & UVa problems/Translated problem

PKU 1163. The Triangle

The Triangle
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 13569 Accepted: 7789

Description

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

(Figure 1)
Figure 1은 숫자로 이루어진 삼각형입니다. 맨 위에서 시작해서 맨 아래의 한 지점에서 끝나는 임의의 길을 지나는 숫자들의 합들 중 가장 큰 것을 계산하는 프로그램을 만드세요. 각 스텝에서는 왼쪽아래 또는 오른쪽아래로 갈 수 있습니다.

Input

당신의 프로그램은 표준 입력으로 읽어들입니다. 첫째 줄은 하나의 정수 N을 포함하는데, 이것은 삼각형의 행의 개수를 의미합니다. 그 뒤의 N개 줄은 삼각형의 데이터를 서술합니다. 삼각형의 행의 개수는 1보다는 크고 100보다는 작거나 같습니다. 삼각형 안의 숫자들은 모두 정수이며, 0보다 크거나 같고 99보다 작거나 같습니다.

Output

당신의 프로그램은 표준 출력으로 써내려갑니다. 정수로 된 합들 중 가장 큰 것을.

Sample Input

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

Sample Output

30

Source




*역자 주
1. 약간 졸립기도 하고, 영어가 부족한 것도 있고 해서 번역이 깔끔하지 못할 것입니다 =_= 고칠만한 부분은 댓글로 달아주세요//
2. 예시에 나온 삼각형은 7, 3, 8, 7, 5 순서로 타고 내려가면 그 합이 30이 되고, 다른 어떤 길 위의 합도 30보다 크지 않습니다

'PKU & UVa problems > Translated problem' 카테고리의 다른 글

PKU 2840. Big Clock  (0) 2009.05.11
PKU 2656. Unhappy Jinjin  (3) 2009.05.05
PKU 2039. To and Fro  (3) 2009.03.25
UVa 324. Factorial Frequencies  (6) 2009.03.17
PKU 1455. Crazy Tea Party  (12) 2009.02.25