Level 3. 정수 삼각형

정수 삼각형 [동적 계획법(DP)]

코딩테스트 연습 > 동적계획법 > 정수 삼각형

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

문제 구상

• 입력: 삼각형의 정보가 담긴 배열(triangle)
• 출력: 거쳐간 숫자의 최대값
• 구상:
  • 거쳐간 숫자의 최대값은 trianle의 -1번째 리스트 중 가장 큰 값입니다.
  • 메모이제이션을 하여 상향식으로 해당 문제를 풀 수 있습니다.
  1. 맨 밑줄 값이 저장되고, 나머지 줄은 빈 리스트로 구성된 리스트를 생성합니다.
  2. 맨 밑줄 부터 위로 올라가며, 해당 위치의 값 + 바로 윗줄의 같은 위치의 값과 해당 위치의 값 + 바로 윗줄의 다음 위치의 값 중 최대값을 윗줄의 리스트에 삽입합니다.
  3. 위의 과정을 수행한 뒤, 가장 앞의 리스트값을 출력합니다.

문제 풀이

#00
triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
#01 메모이제이션 - 맨 밑줄 저장 -> 상향식
answer = [[] for _ in range(len(triangle)-1)]+[triangle[-1]]
#02
for i in range(len(triangle)-1,0,-1): # cols
    for j in range(0,len(triangle[i-1])): # rows
        answer[i-1].append(max(answer[i][j] + triangle[i-1][j],answer[i][j+1] + triangle[i-1][j]))
#03
print(answer)
print(max(answer)[0])

전체 코드

def solution(triangle):
    answer = [[] for _ in range(len(triangle)-1)]+[triangle[-1]]

    for i in range(len(triangle)-1,0,-1): # cols
        for j in range(0,len(triangle[i-1])): # rows
            answer[i-1].append(max(answer[i][j] + triangle[i-1][j],answer[i][j+1] + triangle[i-1][j]))
    return max(answer)[0]