시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 15672 8925 6510 57.800%

문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1

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

예제 출력 1

30
W3sicHJvYmxlbV9pZCI6IjE5MzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMyMTggXHVjMGJjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cHJlPlxyXG4gICAgICAgIDdcclxuICAgICAgMyAgIDhcclxuICAgIDggICAxICAgMFxyXG4gIDIgICA3ICAgNCAgIDRcclxuNCAgIDUgICAyICAgNiAgIDU8XC9wcmU+XHJcblxyXG48cD5cdWM3MDQgXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDA2Y1x1YWUzMFx1YWMwMCA1XHVjNzc4IFx1YzgxNVx1YzIxOCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTVjIFx1YmFhOFx1YzJiNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU4IFx1YzcwNFx1Y2UzNSA3XHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YzVlYyBcdWM1NDRcdWI3OThcdWNlMzVcdWM3M2NcdWI4NWMgXHViMGI0XHViODI0XHVjNjJjIFx1YjU0YywgXHVjNzc0XHVjODFjXHVhZTRjXHVjOWMwIFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLiBcdWM1NDRcdWI3OThcdWNlMzVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjZTM1XHVjNWQwXHVjMTFjIFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWMyMThcdWM3NTggXHViMzAwXHVhYzAxXHVjMTIwIFx1YzY3Y1x1Y2FiZCBcdWI2MTBcdWIyOTQgXHViMzAwXHVhYzAxXHVjMTIwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzgzIFx1YzkxMVx1YzVkMFx1YzExY1x1YjljYyBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSA1MDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjMDEgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmM5NFx1YzcwNFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSA5OTk5IFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMCBuKDEgJmxlOyBuICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgbisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWM4MTVcdWMyMTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwJm5ic3A7XHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxOTMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFRyaWFuZ2xlIiwiZGVzY3JpcHRpb24iOiI8cHJlPlxyXG4gICAgICAgIDdcclxuICAgICAgMyAgIDhcclxuICAgIDggICAxICAgMFxyXG4gIDIgICA3ICAgNCAgIDRcclxuNCAgIDUgICAyICAgNiAgIDUgKEZpZ3VyZSAxKTxcL3ByZT5cclxuXHJcbjxwPkZpZ3VyZSAxIHNob3dzIGEgbnVtYmVyIHRyaWFuZ2xlLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBoaWdoZXN0IHN1bSBvZiBudW1iZXJzIHBhc3NlZCBvbiBhIHJvdXRlIHRoYXQgc3RhcnRzIGF0IHRoZSB0b3AgYW5kIGVuZHMgc29tZXdoZXJlIG9uIHRoZSBiYXNlLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkVhY2ggc3RlcCBjYW4gZ28gZWl0aGVyIGRpYWdvbmFsbHkgZG93biB0byB0aGUgbGVmdCBvciBkaWFnb25hbGx5IGRvd24gdG8gdGhlIHJpZ2h0LjxcL2xpPlxyXG5cdDxsaT5UaGUgbnVtYmVyIG9mIHJvd3MgaW4gdGhlIHRyaWFuZ2xlIGlzICZnZTsgMSBidXQgJmxlOyA1MDAuPFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXJzIGluIHRoZSB0cmlhbmdsZSwgYWxsIGludGVnZXJzLCBhcmUgYmV0d2VlbiAwIGFuZCA5OTk5IChpbmNsdXNpdmUpLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5EYXRhIGFib3V0IHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgdHJpYW5nbGUgYXJlIGZpcnN0IHJlYWQgZnJvbSB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGhpZ2hlc3Qgc3VtIGlzIHdyaXR0ZW4gYXMgYW4gaW50ZWdlciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Olympiad in Informatics > IOI 1994 1번