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

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

프로그래머스

아이디어

• triangle배열을 dp 배열로 재사용해도 문제가 없어 보인다.
• 각 노드에 갈 수 있는 최대 값을 triangle테이블에 덮어쓰기 
• 점화식: triangle[i][j] +=  max(triangle[i-1][j-1], triangle[i-1][j]) 
• dp의 가장 깊은 층의 최댓값을 반환 -> max 두 번 쓰면 될 듯?

코드

def solution(triangle):
    # 양 사이드는 미리 구한다
    for i in range(1, len(triangle)):
        triangle[i][0] += triangle[i-1][0]
        triangle[i][i] += triangle[i-1][i-1]
        
    # 나머지 dp배열도 채워준다
    for i in range(2, len(triangle)):
        for j in range(1, len(triangle[i])-1):
            triangle[i][j] +=  max(triangle[i-1][j-1], triangle[i-1][j])
    # 거쳐간 숫자의 최댓값을 return
    return max(max(triangle))

마무리

• 갑자기 ai가 추천해 준 문제라 풀어봤는데 너무 쉬워서 lv.2정도 생각했는데 3이여서 좀 황당..
• 기본적인 dp문제는 이제 술술 풀린다.