(Week5)[DP] 정수 삼각형

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 30분

1. 문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우 찾기

2. 접근 방식

• 이전에 풀었던 문제여서 비교적 쉽게 풀었다. 

점화식: $dp[i][j] = triangle[i][j] + max(dp[i-1][j], dp[i][j-1])$  
△▲△ (빈 삼각형은 삼각형 값이 없는 부분)   
  ▲▲ (right만 존재하는 경우와, left만 존재하는 경우)

3. 코드

def solution(triangle):   
    dp = [[0]*(i+1) for i in range(len(triangle))]
    dp[0][0] = triangle[0][0]
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            left = 0 if j==0 else dp[i-1][j-1]
            right = 0 if j==len(triangle[i])-1 else dp[i-1][j]
            dp[i][j] = triangle[i][j] + max(left, right)
    return max(dp[-1])

4. 코멘트

• DP는 먼저 점화식을 세워놓고 하면 문제 풀이가 쉬운 것 같다. 
• 대개 0번를 채워놓고 1번째 인덱스부터 시작한다는 것을 생각하면 쉽다. 
• 점화식: 어떤 수열의 항 사이에 성립하는 관계식을 의미한다.