백준 1932 - 정수 삼각형 (Python3)

코드

n = int(input())

dp = []

for _ in range(n):
    dp.append(list(map(int, input().split())))

def tri_sum(n, dp):
    # 전층의 개수 + 1 == 현재 층
    for i in range(1, n):
        for j in range(i+1):

            # 왼쪽 위에서 내려오는 경우
            if j == 0:
                left_down = 0
            else:
                left_down = dp[i-1][j-1]

            # 바로 위에서 내려오는 경우
            if j == i:
                down = 0
            else:
                down = dp[i-1][j]

            # 가장 큰 값 선택
            dp[i][j] = dp[i][j] + max(left_down, down)

    print(max(dp[n-1]))  
    
tri_sum(n, dp)    

문제 해설

DP 문제.

아래층으로 내려가면서 맨 아래층에 도달할 때 누적 합이 최대가 되는 경로를 찾는 문제이다.

점화식의 경우 이전 층의 정수 (바로 윗 값, 왼쪽 윗 값) 중 더 큰 값을 선택하여 현재 층의 값에 더해주는 형식이다.

단, 왼쪽 위와 바로 위의 값이 존재하지 않는 경우, indexOutofRange 에러가 발생하므로

# 왼쪽 위에서 내려오는 경우
if j == 0:
	 left_down = 0
else:
	 left_down = dp[i-1][j-1]

# 바로 위에서 내려오는 경우
if j == i:
	down = 0
else:
	down = dp[i-1][j]

위의 코드와 같이 조건을 걸어 에러 발생을 막아준다. (존재하지 않으므로 값을 0으로 만듬)

또한 문제에서 예시가 정삼각형 형식인 것을 그냥 직각삼각형으로 숫자들을 배열하고 단순하게 왼쪽 위, 바로 위 두가지 경우로 분기하여 풀었다. (아래 그림 참고)