[Python][CodingTest] 정수 삼각형 - 동적 계획법(Dynamic Programmging)

- 프로그래머스 주소 링크
: https://school.programmers.co.kr/learn/courses/30/lessons/43105

접근 방식 

삼각형을 역삼각형으로 만들어 준 뒤, 역방향으로 쭉 더해서 큰값들을 계속해서 더해준다.

역삼각형으로 만들어 주었음

""" 역삼각형으로 뒤집어 준다. """ 
trg = triangle[::-1] 

for i in range(len(trg)):
    # print("=========i 값이 ", i+1, "번째 입니다.==========")
    for j in range(len(trg[i])-1):

i = 0, j = 0 인 경우

i = 1, j = 0인 원소는
i = 0, j = 0 인 원소와 i = 0, j = 1 인 원소 중 큰 값을 더해준 값이 된다.

trg[i+1][j] = trg[i+1][j] + max(trg[i][j], trg[i][j+1])

여기서 for j in range(len(trg[i]-1) 을 보면
1일 빼주고 있다는 걸 알 수 있는데 

i 값이 올라갈 때마다 원소의 개수가 5개 -> 4개 -> 3개 -> 2개 -> 1개로 
줄어들고 있으므로, 일부러 1개만큼 빼주었다.(아래 그림 참고)

i = 0 일때는 4회 연산
i = 1 일때는 3회 연산
i = 2 일때는 2회 연산
i = 3 일때는 1회 연산

triangle의 원소는 총 5개 이지만, 연산은 총 4회 하게된다. 
그래서 1을 빼주었다.

풀이

def solution(triangle):
    trg = triangle[::-1] """ 역삼각형으로 뒤집어 준다. """ 
    for i in range(len(trg)):
        # print("=========i 값이 ", i+1, "번째 입니다.==========")
        for j in range(len(trg[i])-1):
            # print("-------j 값이 ", j+1, "일때-------")
            trg[i+1][j] = trg[i+1][j] + max(trg[i][j], trg[i][j+1])
            # print(trg[i+1][j])
    answer = trg[-1][-1]
    return answer

출력 결과