[프로그래머스]정수 삼각형

[75] 정수 삼각형

책 구매하기

문제 정보

• 분류: 동적 계획법
• 정답률: 60%
• 권장 시간 복잡도: O(R^2)
• 핵심 키워드: 삼각형 DP, 누적 최대합, 바닥까지, 점화식
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105

문제를 읽을 때 체크할 포인트

각 칸에 도달했을 때의 최대 합만 기억하면 된다. 바로 위에서 올 수 있는 두 경로 중 큰 값을 더해 내려가면 정답이 완성된다.

여기서는 정답 자체보다 '상태를 어떻게 잡을 것인가'가 먼저다. 현재 상태에서 다음 상태로 가는 비용만 잘 세우면, 긴 설명보다 점화식 하나가 더 강하다.

풀이 흐름

1. 삼각형 맨 위를 초기값으로 둔다.
2. 각 행을 내려가며 좌상단, 우상단에서 올 수 있는 최대 합을 계산한다.
3. 마지막 행의 최댓값을 반환한다.

구현할 때 놓치기 쉬운 부분

현재 칸으로 올 수 있는 경로는 바로 위와 왼쪽 위 두 곳뿐이다. 경계에 있는 칸은 이 둘이 모두 존재하지 않으므로 첫 줄과 양 끝 처리에서 인덱스 실수가 자주 난다.

파이썬 정답 코드

def solution(triangle):
  # 삼각형 맨 위를 초기값으로 둔다.
  dp = [row[:] for row in triangle]

  # 각 행을 내려가며 좌상단, 우상단에서 올 수 있는 최대 합을 계산한다.
  for r in range(1, len(dp)):
    # 마지막 행의 최댓값을 반환한다.
    for c in range(len(dp[r])):
      if c == 0:
        dp[r][c] += dp[r - 1][c]
      elif c == len(dp[r]) - 1:
        dp[r][c] += dp[r - 1][c - 1]
      else:
        dp[r][c] += max(dp[r - 1][c - 1], dp[r - 1][c])

  return max(dp[-1])

시간 복잡도

R은 삼각형 행 수이다.

삼각형은 1행부터 R행까지 칸 수를 모두 더한 구조라 전체 원소 수가 1+2+...+R이다. 이 합은 R^2 규모이므로 DP도 그 범위 안에서 끝난다.

따라서 시간 복잡도는 O(R^2)이다.