[프로그래머스] Lv.2 정수삼각형 (파이썬) _ 동적프로그래밍(DP)

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

프로그래머스

 

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

---

그 날이 오고야 말았습니다... 알고리즘 이론을 알아야지 문제를 풀 수 있는 날... 오늘 다룰 내용은

---

동적 프로그래밍 (Dynamic Programming, DP)

동적 프로그래밍은 큰 문제를 작은 문제로 쪼개서, 그 결과를 재활용해 문제를 풀어가는 방식입니다.

즉, 같은 부분 문제를 여러 번 계산하지 않고 한 번 계산한 결과를 저장해 두었다가 필요할 때 다시 사용하는 거예요.

 

삼각형 문제에 DP를 적용하는 방법

1. 문제 구조 파악

• 삼각형의 각 칸에서 내려갈 때, 왼쪽 대각선 아래나 오른쪽 대각선 아래로만 이동할 수 있습니다.

• 예를 들어, 어떤 칸의 값이 3이라면, 그 아래 행에서는 8 또는 1로 이동할 수 있습니다.

2. 하위 문제로 쪼개기 (Bottom-Up 접근법)

• 삼각형의 바닥부터 위로 올라가며, 각 칸에서 출발했을 때 바닥까지 도달하는 최대 누적합을 구합니다.

• 바닥의 값은 자기 자신이 최대 누적합입니다.

3. 점화식 만들기

• 만약 삼각형의 i번째 행, j번째 칸의 값을 triangle[i][j]라고 하자.

• 그리고 dp[i][j]를 i행 j열에서 바닥까지 내려가며 얻을 수 있는 최대 합이라고 정의하면,

• 점화식은 다음과 같습니다:

dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])

 

* 여기서 포인트는 바닥에서 위로 올라가면서 최대 누적합을 구한다는 것!

---

나의 풀이

def solution(triangle):
	for i in range(len(triangle)-2, -1, -1): #바닥 바로 위칸 부터 꼭대기층으로 반대로 올라가기
    	for j in range(len(triangle[i])): #i번째 층의 왼쪽부터 오른쪽까지 순회
        	triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]) #가지쳤을 때 큰 값 +
    
    return triangle[0][0]

• 기본 구조라 그런지 이해'는' 됨... 이걸 응용할 수 있을 것인가...