[프로그래머스] 정수 삼각형 by 파이썬 (Python) : 동적 계획법 (Dynamic programming)

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

프로그래머스

 

난이도

LV3

 

 

문제 설명

삼각형 모양으로 꼭대기에서 바닥까지 이어지는 경로 중 숫자의 합이 최대가 되는 경우의 합을 Return해준다.

아래칸으로 이동할때 대각선 방향으로 한칸 오른쪽 왼쪽 으로만 이동 가능하다.

 

 

접근법

삼각형 꼭대기 한칸 아래에서부터 위에서 내려올 수 있는 경우에 대해 최대 값을 더해준다.

만약 양끝에 있는 경우에는 가능한 값이 하나밖에 없으므로 별도로 처리해준다.

내려오면서 가능한 수 중 항상 최대 값을 선택하기때문에 마지막 줄에 저장된 가장 큰 수를 Return 해주면 가능한 경로 중 최대의 수이다.

 

 

코드

def solution(triangle):
    arr = triangle
    for i in range(1, len(triangle)):
        for j in range(len(arr[i])):
            # 가장 왼쪽인 경우
            if j == 0:
                arr[i][j] += arr[i-1][0]
            # 가장 오른쪽인 경우
            elif j == len(arr[i])-1 :
                arr[i][j] += arr[i-1][-1]
            else:
                arr[i][j] += max(arr[i-1][j-1], arr[i-1][j])
    
    return max(arr[-1])

 

 

---

동적계획법(Dynamic Programming)?

https://h-castle.tistory.com/entry/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95-Dynamic-ProgrammingDP

[동적 계획법] 알고리즘 - 동적 계획법 Dynamic Programming(DP)