[Python] 백준 #1932 정수 삼각형

1932번: 정수 삼각형 (acmicpc.net)

1932번: 정수 삼각형

[알고리즘]

DP

 

[접근 방법]

• 각 층의 양 끝에 있는 수 → 바로 위의 수와 그대로 더해진다
• 중간에 있는 수 → 바로 위의 두 수 중, 더 큰 수와 더해진다

→ 이 방법으로 맨 아래층까지 더하면, n개의 경우의수가 구해지고(n = 층수) , 그 중 가장 큰 수를 출력한다.

 

[코드]

n = int(input())
D = []
for _ in range(n):
    D.append(list(map(int, input().split())))
for i in range(1, n) :
    for j in range(len(D[i])) :
        if j == 0 :
            D[i][j] = D[i][j] + D[i - 1][j]
        elif j == i :
            D[i][j] = D[i][j] + D[i - 1][j - 1]
        else :
            D[i][j] = D[i][j] + max(D[i - 1][j - 1], D[i - 1][j])
 
print(max(D[n - 1]))