시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 14608 8289 6056 58.030%

문제

        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+XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSA1MDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjMDEgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmM5NFx1YzcwNFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSA5OTk5IFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMCBuKDEgJmxlOyBuICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgbisxXHVjOTA0XHVhZTRjXHVjOWMwIFx1YzgxNVx1YzIxOCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAmbmJzcDtcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE5MzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgVHJpYW5nbGUiLCJkZXNjcmlwdGlvbiI6IjxwcmU+XHJcbiAgICAgICAgN1xyXG4gICAgICAzICAgOFxyXG4gICAgOCAgIDEgICAwXHJcbiAgMiAgIDcgICA0ICAgNFxyXG40ICAgNSAgIDIgICA2ICAgNSAoRmlndXJlIDEpPFwvcHJlPlxyXG5cclxuPHA+RmlndXJlIDEgc2hvd3MgYSBudW1iZXIgdHJpYW5nbGUuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIGhpZ2hlc3Qgc3VtIG9mIG51bWJlcnMgcGFzc2VkIG9uIGEgcm91dGUgdGhhdCBzdGFydHMgYXQgdGhlIHRvcCBhbmQgZW5kcyBzb21ld2hlcmUgb24gdGhlIGJhc2UuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+RWFjaCBzdGVwIGNhbiBnbyBlaXRoZXIgZGlhZ29uYWxseSBkb3duIHRvIHRoZSBsZWZ0IG9yIGRpYWdvbmFsbHkgZG93biB0byB0aGUgcmlnaHQuPFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgdHJpYW5nbGUgaXMgJmdlOyAxIGJ1dCAmbGU7IDUwMC48XC9saT5cclxuXHQ8bGk+VGhlIG51bWJlcnMgaW4gdGhlIHRyaWFuZ2xlLCBhbGwgaW50ZWdlcnMsIGFyZSBiZXR3ZWVuIDAgYW5kIDk5OTkgKGluY2x1c2l2ZSkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPkRhdGEgYWJvdXQgdGhlIG51bWJlciBvZiByb3dzIGluIHRoZSB0cmlhbmdsZSBhcmUgZmlyc3QgcmVhZCBmcm9tIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgaGlnaGVzdCBzdW0gaXMgd3JpdHRlbiBhcyBhbiBpbnRlZ2VyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 1994 1번