[Python] 정수 삼각형 (Programmers Lv. 3)

문제 설명

문제 설명

제한 사항

제한 사항

입출력 예

입출력 예

풀이

주어진 문제에 대한 최적값을 구하는 것이기 때문에 Dynamic Programming(동적 계획법)으로 접근해볼 수 있습니다.

하위 문제의 수가 기하급수적으로 증가할 때 유용한 접근법입니다.

즉, 하위 문제를 해결하는 과정에서 DP Table을 채우면서 주어진 문제를 해결할 수 있는 방법이라고 할 수 있습니다.

Dynamic Programming

해설

(x, y)에서부터 시작한다고 하면, (x, y+1), (x+1, y+1)을 계산해 최댓값을 계속 저장하게 됩니다.

(x, y)에서 계산된 (x, y+1), (x+1, y+1)과 (x+1, y)에서 계산된 (x+1, y+1), (x+2, y+1) 중에서 (x+1, y+1)이 겹칩니다.
매 계산마다 현재 해당 좌표에 저장된 값과 새로 계산된 값의 크기를 비교해 최댓값만 취하게 되면 결국 마지막에는 다양한 경로를 통해 바닥으로 도착한 최댓값들을 알 수 있습니다.

바닥에 해당하는 테이블에서 가장 큰 값을 취하면 문제를 해결할 수 있습니다.

코드

def solution(triangle):
  n = len(triangle)							# 삼각형 높이
  table = [[0]*i for i in range(1, n+1)]	# DP Table 초기화
    
  table[0][0] = triangle[0][0]				# 초기값 설정
    
  for y in range(n-1):						# Bottom-up
    for x in range(len(triangle[y])):
      table[y+1][x] = max(table[y+1][x], table[y][x]+triangle[y+1][x])			# 대각선 왼쪽
      table[y+1][x+1] = max(table[y+1][x+1], table[y][x]+triangle[y+1][x+1])	# 대각선 오른쪽
 
  return max(table[-1])

실행 결과

실행 결과