[프로그래머스] 정수 삼각형 - DP - Lv.3

문제 링크

프로그래머스

 

풀이

 

 

1차 시도

처음에는 단순하게 재귀를 통한 완전 탐색으로 풀려고 했다.

max_height = 0
max_result = 0

def solution(triangle):
    global max_height
    max_height = len(triangle)
    visit(0,0,0,triangle)
    return max_result
    
def visit(i,j, cur_sum, triangle):
    global max_height
    if i == max_height:
        global max_result
        max_result = cur_sum if cur_sum > max_result else max_result
        return
    
    # 다음 행의 j와 j+1 방문
    next_sum = cur_sum + triangle[i][j]
    visit(i+1, j, next_sum, triangle)
    visit(i+1, j+1, next_sum, triangle)

하지만 삼각형의 높이는 최대 500이고, 깊이가 깊어질 수록 경우의 수가 2^높이 개가 되기 때문에, 사실상 최악의 알고리즘 복잡도이라고 봐야한다. (2^500..)

 

DP

동적 계획법은 현재의 결과가 이전의 결과에 영향을 받을 때, 그리고 이러한 영향이 다음에도 이어질 때 쓰기 좋다.

 

실제 알고리즘 정의는 하나의 큰 문제를 여러개의 작은 문제로 나누고, 작은 문제를 해결해서 얻은 결과를 기반으로 큰 문제를 해결할 때 사용하는 알고리즘이다.

그런데, 이렇게 말하면 이해하기가 어렵고, 적용하기도 어렵다고 생각한다.

 

일반적으로는 문제를 기반으로 어떤 점화식을 세울 수 있다면, DP를 적용할 법한 문제라고 보면 된다.

 

이 문제도 마찬가지다.

 

2차 시도 (DP를 이용한)

 

1이라는 숫자를 가지고 문제를 풀어보자.

 

이 문제는 우선, 위에서부터 아래로 대각선(왼아래 or 오른아래)으로 타고 타고 내려가면서 값을 더했을 때 언제 값이 제일 큰지 구하는 것이다.

 

 

현재 1에 도달했다면,  3이나 8에서 내려온 경우다.

 

즉, 현재 삼각형의[i][j]의 이전에 지나온 값은 [i-1][j-1]거나 [i-1][j]이다.

이 때, [i-1][j-1]까지 지나온 지점의 합의 최대값과 [i-1][j]까지 지나온 지점의 합의 최대값 중에 더 큰 값을 채택하고, [i][j]값을 더하면 [i][j]까지 지나온 지점의 합의 최대값이 된다.

 

즉 i-1까지 구한 값을 가지고 i의 값을 구할 수 있으며, i에서 구한 값을 가지고 i+1의 값을 구할 수 있는 점화식 구조가 완성되었다.

정리하면 다음과 같다.

 

[점화식 구조]

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

 

예외 처리

1. j=0이라면 DP[i-1][-1]에 접근하는 위험이 생기고,

2. j=i 라면 DP[i-1][i]에 접근하는 위험이 생긴다.

 

1은 직관적으로 이해가 되겠지만 2번이 이해되지 않을 수 있는데,

 

DP[3][3] = max(DP[2][2], DP[2][3]) + Triangle[3][3]

여기서 에러가 발생한다.

 

따라서 j가 0일 때, i일 때, 그 외일 때에 대한 분기를 두어 코드를 처리하였다.

 

최종 코드

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

    return(max(DP[-1]))

 

후기

완탐으로 접근하면 시간 초과가 나는 것도 그렇고, 점화식이 바로 나오는 것도 그렇고 전형적인 DP 문제였다.

하지만 단순하게 생각하고 놓친 것이 아쉽다.