다이나믹프로그래밍(DP) #프로그래머스 #정수 삼각형 | 파이썬 풀이

📚 문제

원본: https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3 

코딩테스트 연습 - 정수 삼각형

🔥 접근법

문제를 보자마자 전형적인 다이나믹 프로그래밍(Dynamic Programming, DP) 유형의 문제라고 생각합니다.

유사한 접근법을 사용한 DP 문제로서 "최저 비용의 노드만 거쳐 미로를 탈출하는 문제"를 접한 경험이 있습니다.

 

본 문제의 핵심 전략은 다음과 같습니다.

삼각형 맨 아래부터 2개의 인접한 자식 노드 중 큰 값을 부모 노드에 더해 부모 노드를 업데이트해 나가는 것입니다.

즉, 자식 노드가 포함된 한 줄과 부모 노드가 포함된 한 줄을 리스트에서 각각 꺼내고,

부모 노드 각각을 최대한 큰 자식 노드와의 합으로 업데이트해 나가는 것이죠.

💻 소스코드

def solution(triangle):
    while len(second) > 1:
        first = triangle.pop()
        second = triangle.pop()
        for i in range(len(second)):
            if first[i] < first[i+1]:
                second[i] += first[i+1]
            else:
                second[i] += first[i]
        triangle.append(second)
    return second[0]

접근법만큼 간단하게 구현해 볼 수 있는 문제였습니다.

👀 참고할 만한 포스팅

1.  [알고리즘] 다이나믹(동적) 프로그래밍에 대해 알아보자! (+Python 구현)

---

아낌없는 피드백 & 질문 환영합니다 :)

아래에 👇👇👇 댓글 남겨주세요!

그럼 오늘도 즐거운 하루 보내시길 바랍니다.

고맙습니다.