[프로그래머스 Lv.3] 정수 삼각형(DP)

🍇문제

 

🍇풀이방법

삼각형 모양의 숫자 배열에서, 꼭대기에서부터 시작하여 아래로 내려오면서 숫자를 더해 나갈 때, 가장 큰 합을 찾는 문제이다. 각 위치에서는 그 위치까지 도달할 수 있는 두 가지 경로가 존재하며, 이전 단계에서 선택된 최적 경로의 값을 고려해야 한다.

 

<접근 방식> 

이 문제는 Dynamic Programming(동적 계획법)을 사용하여 해결할 수 있다. 각 위치에서 최적의 경로를 선택하여 문제를 해결해보자.

 

1. DP 테이블 초기화

dp = [] for lst in triangle: dp.append([0] * len(lst))

 

dp 리스트는 삼각형 모양의 구조를 가지며, 각 위치에서의 최댓값을 저장하는 데 사용된다.

dp[i][j]는 삼각형의 i번째 행, j번째 열에 위치한 값까지 도달하는 최댓값을 의미한다.

 

2. 초기값 설정

dp[0][0] = triangle[0][0]

 

삼각형의 맨 위에 있는 첫 번째 요소(꼭짓점)로 dp[0][0]을 초기화한다

 

3. 왼쪽 빗면과 오른쪽 빗면 처리

 

=> 각 행의 첫 번째와 마지막 요소 처리

 

for i in range(1, len(triangle)):
	dp[i][0] = triangle[i][0] + dp[i-1][0] 
    	dp[i][-1] = triangle[i][-1] + dp[i-1][-1]

 

삼각형의 각 행에서 첫 번째와 마지막 요소는 각각 자신의 바로 위에 있는 요소로부터만 영향을 받는다. 

 

 

4. 내부 요소 처리

for i in range(1, len(triangle)):
    for j in range(1, len(triangle[i]) - 1):
        dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j])

 

삼각형의 내부 요소들은 자신이 위치한 자리까지 도달할 수 있는 두 가지 경로(왼쪽 위에서 내려오는 경우 & 오른쪽 위에서 내려오는 경우)를 고려해 최댓값을 선택한다.

 

5. 최종 결과 도출

answer = max(dp[-1]) return answer

 

 

마지막 행에서 가장 큰 값을 반환한다. 이 값이 꼭대기에서 삼각형의 바닥까지 내려오는 동안의 최대 합이 된다!

 

🍇코드

#각 위치에서는, max(내 왼쪽 위까지합 , 내 오른쪽 위까지 합)

def solution(triangle):
    
    dp = []
    for lst in triangle:
        dp.append([0] * len(lst)) #   [[0], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0]]
    dp[0][0] = triangle[0][0]
    #왼쪽 빗면,오른쪽 빗면은 한쪽 방향에서만 내려옴
    for i in range(1,len(triangle)): #   [[7], [10, 15], [18, 0, 15], [20, 0, 0, 19], [24, 0, 0, 0, 24]]
        dp[i][0]= triangle[i][0] + dp[i-1][0]
        dp[i][-1]= triangle[i][-1] + dp[i-1][-1]
    
    print(dp)
    for i in range(1,len(triangle)):
        for j in range(1, len(triangle[i]) - 1):
            dp[i][j] = triangle[i][j] + max(dp[i-1][j-1],dp[i-1][j])
            
    

    answer = max(dp[-1])
    return answer