[프로그래머스/파이썬] 정수 삼각형

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

프로그래머스

프로그래머스에서 dp 문제 풀었다.

그런데 왠걸,, 백준에서 이미 비슷한 문제를 풀어본 적이 있었기에 금방 풀었다 ㅎㅎ

level 3의 다른 카테고리 문제들보면 좀 까다로운 경우가 많은데, 아무래도 dp인지라 기본적으로 level이 좀 높게 잡히는 것 같다.

 

그래도 이 문제는 크게 어려운 점화식도 아니니 찬찬히 코드 보면서 손으로 따라가면 금방 이해하실 수 있을 것 같다.

def solution(triangle):
    answer = 0
    dp = [[0 for _ in range(len(triangle))] for _ in range(len(triangle))]
    dp[0][0] = triangle[0][0]

    for i in range(1,len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                dp[i][0] = dp[i-1][0] + triangle[i][0]
            elif j == len(triangle[i]) - 1:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1] + triangle[i][j], dp[i-1][j] + triangle[i][j])
            #print(i,j,dp[i][j])

    answer = max(max(dp))
    return answer