백준 1932번. 정수 삼각형 (Python / 파이썬)

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

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

출력

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

---

문제 풀이

정수 삼각형이 주어졌을 때, 맨 위층부터 시작해서

대각선 왼쪽 또는 대각선 오른쪽 아래에 있는 수 중 하나를 선택하여

아래층으로 내려올 때 선택된 수의 합이 최대가 되는 경로를 구하는 문제입니다.

 

각 경우의 최대값을 기억해야 하므로

DP를 이용해 문제를 해결했습니다.

 

먼저 삼각형의 정수값을 입력 받으면 위와 같은 형태로 list에 저장이 됩니다.

따라서 대각선 왼쪽은 바로 아래의 수가 되고,

대각선 오른쪽은 오른쪽 아래의 수가 됩니다.

아래의 있는 수 입장에서 보면 바로 위 혹은 왼쪽 위에서 순서가 내려옵니다.

 

맨 위의 층을 제외하고 두번째 층부터, 그리고 각 층은 맨 왼쪽부터 

오른쪽까지 반복문을 수행합니다.

만약 맨 왼쪽에 있는 원소라면 왼쪽 위에서 내려오는 순서는 없습니다.

또한 만약 맨 오른쪽에 있는 원소라면 바로 위에서 내려오는 순서는 없습니다.

따라서 이 경우를 모두 0으로 설정해주었습니다.

 

이 경우를 제외하고는 위에서 내려오는 값, 왼쪽 위에서 내려오는 값 중

최대값을 구하고 더해주어 list의 값을 갱신시켜주었습니다.

이 과정을 반복하고 나면 맨 아래줄에는 각 경우의

최대값이 저장되게 됩니다.

따라서 맨 아래줄에서 최대값을 고르면 답이 됩니다.

---

My Code

n = int(input()) # 삼각형의 크기

dp = []
for _ in range(n):
    dp.append(list(map(int,input().split()))) # 정수 삼각형

for i in range(1, n): # 두번째 층부터
    for j in range(i + 1): # i와 같을 때까지만 오른쪽으로 이동
        if j == 0: # 맨 왼쪽 원소라면
            left_up = 0 # 왼쪽 위에서 오는 원소 없음
        else: 
            left_up = dp[i - 1][j - 1] # 왼쪽 위에서 오는 원소
        if j == i: # 맨 오른쪽 원소라면
            up = 0 # 위에서 오는 원소 없음
        else:
            up = dp[i - 1][j] # 위에서 오는 원소
        dp[i][j] += max(left_up, up) # 둘 중 최대값을 더해주어 갱신

print(max(dp[n - 1])) # 맨 아래줄에서 최대값을 출력