백준 온라인 저지, 다이나믹프로그래밍 / 1932번: 정수삼각형 (파이썬 / , 백준 브론즈문제)

문제

        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+XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSA1MDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFjMDEgXHVjMjE4XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmM5NFx1YzcwNFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSA5OTk5IFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMCBuKDEgJmxlOyBuICZsZTsgNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgbisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWM4MTVcdWMyMTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwJm5ic3A7XHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxOTMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFRyaWFuZ2xlIiwiZGVzY3JpcHRpb24iOiI8cHJlPlxyXG4gICAgICAgIDdcclxuICAgICAgMyAgIDhcclxuICAgIDggICAxICAgMFxyXG4gIDIgICA3ICAgNCAgIDRcclxuNCAgIDUgICAyICAgNiAgIDUgKEZpZ3VyZSAxKTxcL3ByZT5cclxuXHJcbjxwPkZpZ3VyZSAxIHNob3dzIGEgbnVtYmVyIHRyaWFuZ2xlLiBXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBoaWdoZXN0IHN1bSBvZiBudW1iZXJzIHBhc3NlZCBvbiBhIHJvdXRlIHRoYXQgc3RhcnRzIGF0IHRoZSB0b3AgYW5kIGVuZHMgc29tZXdoZXJlIG9uIHRoZSBiYXNlLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkVhY2ggc3RlcCBjYW4gZ28gZWl0aGVyIGRpYWdvbmFsbHkgZG93biB0byB0aGUgbGVmdCBvciBkaWFnb25hbGx5IGRvd24gdG8gdGhlIHJpZ2h0LjxcL2xpPlxyXG5cdDxsaT5UaGUgbnVtYmVyIG9mIHJvd3MgaW4gdGhlIHRyaWFuZ2xlIGlzICZnZTsgMSBidXQgJmxlOyA1MDAuPFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXJzIGluIHRoZSB0cmlhbmdsZSwgYWxsIGludGVnZXJzLCBhcmUgYmV0d2VlbiAwIGFuZCA5OTk5IChpbmNsdXNpdmUpLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5EYXRhIGFib3V0IHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGUgdHJpYW5nbGUgYXJlIGZpcnN0IHJlYWQgZnJvbSB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGhpZ2hlc3Qgc3VtIGlzIHdyaXR0ZW4gYXMgYW4gaW50ZWdlciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

코드

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
d = [[0 for _ in range(i)] for i in range(1, n+1)]
for i in range(n):
    d[n-1][i] = graph[n-1][i]


def find_max_value(depth, index):
    if depth == n-1 or d[depth][index]:
        return d[depth][index]

    max_value = 0
    for i in range(index, index+2):
        value = find_max_value(depth+1, i)
        max_value = max(value, max_value)
    d[depth][index] = max_value + graph[depth][index]
    return d[depth][index]

find_max_value(0, 0)
print(d[0][0])