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

문제

출처

이해

입력

• triangle
  • 타입: 배열
  • 길이: [1, 500]
  • 원소
    • 타입: 배열
    • 길이: [1, 500]
    • 원소
      • 타입: 정수
      • 범위: [0, 99]

출력

• 꼭대기에서 바닥까지 내려갈 때, 거쳐간 수의 합이 가장 큰 경우

조건

1. 삼각형의 아래로만 갈 수 있다.
2. 아래 칸으로 이동할 때 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동할 수 있다.

예시

입출력

입력: 
[[7], 
[3, 8], 
[8, 1, 0], 
[2, 7, 4, 4], 
[4, 5, 2, 6, 5]]

출력: 
30

접근

문제의 설명은 정삼각형으로 주어지지만, 입력은 직각삼각형이다. 주어진 조건을 arr의 index에 맞춰서 다시 해석하면 다음과 같다.

m행 n열에서 m+1행 n열 또는 m+1행 n+1열로만 갈 수 있다.

조건에 따르면 m행 n열에 관여할 수 있는 위치는 m-1행 n-1열 또는 m-1행 n열이다. 여기서 다음과 같은 정의를 생각해보자.

DP[i][j] = i행 j열에 도달하는 경로 중 거쳐간 수의 합이 가장 큰 경우의 그 합

그럼 조건을 다음 점화식으로 표현할 수 있다.

DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + T[i][j]

이제 이 점화식을 코드로 옮기면 끝난다. 점화식의 초기값인 0행 0열은 자연스럽게 triangle[0][0]이 된다. 단 주의해야할 점은 직각삼각형의 좌변과 빗변의 경우 해당 점화식을 적용할 때 각각 (i-1, j-1), (i-1, j)가 정의되지 않기 때문에 코너 케이스를 처리해야 한다는 것이다.

구현

def solution(triangle):
    answer = 0
    n = len(triangle)
    DP = [[0] * n for _ in range(n)]
    DP[0][0] = triangle[0][0]
    
    for i in range(1, n):
        for j in range(0, i+1):
            if j == 0:
                DP[i][j] = DP[i-1][j]
            elif j == i:
                DP[i][j] = DP[i-1][j-1]
            else:
                DP[i][j] = max(DP[i-1][j-1], DP[i-1][j])
            DP[i][j] += triangle[i][j]
    
    return max(DP[n - 1])