[프로그래머스] 정수 삼각형

문제

• 삼각형 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우 찾기 
• 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 혹은 왼쪽으로만 이동 가능하다.
• 1 <= 삼각형 높이 <= 500

 

풀이

• 높이가 최대 500이므로 모든 경로를 확인한다면 시간초과!
• DP 를 이용해 왼쪽과 오른쪽 중 어느 루트가 최댓값인지 확인하도록 한다.
• DP[n][i] : n번째 층에서 i 번째로 끝났을 때의 최댓값

 

def solution(triangle):
    answer = 0
    
    # dp[n][i] : n번째 층에서 i번째로 끝났을 때의 최댓값
    dp = [[0] * len(triangle[i]) for i in range(len(triangle))]
    dp[0][0] = triangle[0][0]
	
    for i, layer in enumerate(triangle[1:]) :	# n번째 층
        dp[i+1][0] = dp[i][0] + layer[0]		# 첫번째 값
        for j in range(1, len(layer)-1) :
        	# 왼쪽과 오른쪽 중 어느 루트가 최댓값인지 확인
            dp[i+1][j] = max(dp[i][j-1], dp[i][j]) + layer[j]
        dp[i+1][-1] = dp[i][-1] + layer[-1]		# 마지막 값

    return max(dp[-1])

 

References

• 프로그래머스 고득점Kit DP