프로그래머스 lv3 정수 삼각형 (python)

문제

 

풀이

프로그래머스 lv3라고해서 걱정했지만,

간단한 예외처리를 해주면 되는 DP문제이다.

우선 삼각형 맨 위에 있는 숫자는 dp 배열에 직접 넣어준다.

이후 삼각형의 숫자가 행이 내려갈수록 더해져야 하는데, 그 숫자에 근접한 이전 행의 숫자만 더할 수 있다.

따라서 i행의 j번째숫자는 i-1행의 j번째 숫자와 i-1행의 j-1번째 숫자 중 큰 숫자를 더해주면 되는 것이다.

그리고 각 삼각형 행에 있는 첫번째 숫자일때와 마지막 숫자일때만 예외처리를 해주면 된다.

첫번째일 때는 i-1행의 j번째(첫번째) 숫자를 더해주면 되고,

마지막일 때는 i-1행의 j-1번째 숫자를 더해주면 된다. 

 

코드

def solution(triangle):
    dp=[]
    tri_len=len(triangle)
    for i in range(tri_len):
        temp_list = [0 for _ in range(i+1)]
        dp.append(temp_list.copy())
    dp[0][0]=triangle[0][0]
    for i in range(1,tri_len):
        for j in range(i+1):
            if j==0:
                dp[i][j] = triangle[i][j] + dp[i-1][j]
            elif j==i:
                dp[i][j] = triangle[i][j] + dp[i-1][j-1]
            else:
                dp[i][j] = max(triangle[i][j]+dp[i-1][j-1],triangle[i][j]+dp[i-1][j])
    
    answer = 0
    for i in dp:
        answer = max(answer,max(i))
    return answer