[Python문제풀이-Dynamic Programming] 정수삼각형

2025.03.15 - [프로그래밍/Python 관련 정보] - [Python] Table of Contents

---

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

프로그래머스

 

문제를 보자마자 DP를 생각했다가, 멈칫하게 되는 문제였습니다. 제가 지난 포스팅에서 정리했듯이 Dynamic Programming을 쓰는 상황이라는 것은 "작은 문제에서 정답은 큰 문제에서도 정답"이 되어야 합니다. 그런데, 저는 \(a_{n}\) (그러니까 수열의 항)을 행에서의 최대값으로 두고 풀어보려고 했는데(아래 그림1의 왼쪽).. 이렇게 두었더니 "작은 문제에서 정답은 큰 문제에서도 정답"이라는 전제조건을 만족시킬 수 없었습니다. 예를 들어 바로 직전항까지의 최적의 경로를 구했다고 해봅시다. 그런데 새로 등장하는 행의 저~쪽 끝에 99999와 같은 엄청 큰 값이 있다면? 무조건 그 값을 취하는 path를 답으로 취해야하고 이전의 최적 path는 버려야하는 상황이 되니까요.

그런데, 이것을 행 단위로 생각하는 것이 아니라 원소 하나하나를 '항'으로 두고 그 위치(항)에서 최대합을 먼저 구한다고 해봅시다. 그리고나서 문제에서 원하는 최종 답은 삼각형 마지막 행에서 max 값을 취해주는 방식을 쓴다면? 이제 이러면 "작은 문제에서 정답은 큰 문제에서도 정답"이라는 전제조건을 지킬 수 있게 됩니다. 

그림 1. 저의 최초 풀이방법 (좌) / 올바른 풀이방법 (우)

 

앞에 경로가 어찌되었는지는 일단 잊어버리고  \(b^{(2)}_{1}\) 에 이 위치에서까지 오는데 최대값이 저장되어 있고  \(b^{(2)}_{2}\) 에 역시 그 위치까지 오는데 최대값이 저장되어 있다고 합시다. 그런 상황에서 \(b^{(3)}_{2}\) 까지 오는데 최대값은? 이건 \(b^{(2)}_{1}\)와 \(b^{(2)}_{2}\) 중 더 큰 값에 해당 위치( \(b^{(3)}_{2}\) 의 위치 )에 대응되는 정수삼각형의 값을 더해준 값이겠죠. 일종의 점화식을 만들 수 있게 되었습니다. 

 

대신 행 안에서도 loop를 돌려주어야 하긴하겠죠. 아래와 같은 코드를 쓸 수 있을 겁니다. 

def solution(triangle):
    answer = 0
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:	# 왼쪽 끝
                triangle[i][j] += triangle[i-1][0]  
            elif j == len(triangle[i])-1:	# 오른쪽 끝
                triangle[i][j] += triangle[i-1][-1]	
            else:
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])

    return max(triangle[-1])