[Programmers] 정수 삼각형(Python) / Dynamic Programming

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

 

# 14분 소요

• 사용 알고리즘 : Dynamic Programming(동적 계획법)
• (가장 아래 행-1) 행부터 가장 아래 행의 값들을 참고해 더 큰 값을 선택해 더하면서 현 위치 값을 갱신해 올라온다.
• 가장 상단 행까지 값을 모두 채우면 첫 값(triangle[0][0])을 리턴한다.

 

파이썬 코드는 다음과 같다.

---

def solution(triangle):
    for r in range(len(triangle)-2, -1, -1):
        for c in range(r+1):
            triangle[r][c] += max(triangle[r+1][c], triangle[r+1][c+1])
    return triangle[0][0]

---

• 고찰 : DP는 풀수록 조금씩 느는 것 같다?.. 늘겠지?? 늘거다!!