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

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

코딩테스트 연습 - 정수 삼각형

 

Top Down 방법

def solution(triangle):
    height = len(triangle)
    
    # Top-down 방법으로 풀이
    for i in range(1, height):
        for j in range(i+1):
            print(i, j)
            # 가장 왼쪽의 경우 왼쪽수를 모두 더하면서 내려감
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            # 가장 오른쪽의 경우 오른쪽수를 모두 더하면서 내려감
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            # 그외의 경우 윗단계의 두 수중 큰 값을 더하면서 내려감
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    
    answer = max(triangle[-1])
    return answer

해당 유형의 문제를 풀 때 이용되는 방법으로 2가지가 존재한다. 첫번째는 직관적으로 생각나는 Top Down 방법이다.

즉, 위에서부터 연산을 하면서 아래로 내려가는 방법이다. 

 

문제 해결 Point

해당 문제에서는 내려가는 3가지의 방법이 존재한다.

1. 가장 왼쪽라인만 더하면서 내려가는 경우
2. 가장 오른쪽라인만 더하면서 내려가는 경우
3. 나머지 라인의 경우 더 큰값을 고르면서 내려가는 경우

먼저, 앞의 2가지의 경우는 최댓값을 고를 필요가 없으므로 고정되어있다. 가운데 라인의 경우는 아래 존재하는 두개의 수들중 큰 값을 더하면서 내려가면 된다.

최종적으로 가장 마지막 라인중 최댓값을 출력하면 문제를 해결할 수 있다.

 

Bottom Up 방법

def solution(triangle):
    height = len(triangle)
    
    for i in range(height-1, 0, -1):
        for j in range(i):
            # 바로 윗 단계에서의 최댓값은, 아랫단계 두개중 큰 값과 더한 값이다.
            triangle[i-1][j] += max(triangle[i][j], triangle[i][j+1])
            
    answer = triangle[0][0]
    return answer

 

문제 해결 Point

이번에는 반대의 방법인 Bottom Up 방법이다.

바로 윗단계의 최댓값을 하나 아래에 위치한 두 값중 큰 값과 더한 값으로 갱신해나가면서 꼭대기까지 올라가면 문제를 해결할 수 있다.

 

 

---

 

위에서 제시한 알고리즘으로 모두 풀어보았는데, Top Down의 경우 생각나는대로 직관적으로 코딩을 할 수 있었고, Bottom Up의 경우에는 약간 까다롭지만 코드적으로 깔끔하게 문제를 해결할 수 있다고 생각한다.