📝 정수 삼각형 (Level 3)

동적 계획법 (Dynamic Programming)
정수 삼각형

🔹Python

• 다른 사람의 풀이

# Bottom-Up
def solution(triangle):

    floor = len(triangle) - 1 

    while floor > 0:  
        for i in range(floor):  
            # 위층의 칸에 아래 칸의 두 개중 큰 값을 더해줌
            triangle[floor-1][i] += max(triangle[floor][i], triangle[floor][i+1])
        floor -= 1  # 층하나 올라가기

    return triangle[0][0]

문제 읽고 탐욕법(Greedy)가 아니라 동적 계획법(Dynamic Programming) 문제구나 라는 생각이 들었다. 삼각형의 아래 칸으로 이동할 때 무조건 큰 수를 선택하는 것이 아니라 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하기 때문이다. 그래서 Top-Down 방식으로 코드를 작성하려고 했는데 머리가 돌아가지 않아 다른 분들의 풀이를 봤다.

Bottom-Up 방식으로 바로 위층의 칸에 아래 칸의 두 개중 큰 값을 더해주어서 풀었다.

---

🔸Java

// Bottom-Up (Dynamic Programming)
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int floor = triangle.length - 1;
        while(floor > 0) {
            for(int i = 0; i < floor; i++){
                triangle[floor-1][i] += Math.max(triangle[floor][i], triangle[floor][i+1]);
            }
            floor -= 1;
        }
        answer = triangle[0][0];
        return answer;
    }
}

파이썬 코드를 자바로 변환하였다.

동적 프로그래밍이 사용된 방식

1. 문제를 하위 문제로 분할:
   삼각형의 각 위치에서 최적의 경로를 찾는 문제를, 그 위치 아래에 있는 두 개의 위치 중 최적의 값을 선택하는 문제로 분할합니다. 예를 들어, 삼각형에서 특정 위치 (i, j)의 값은 (i+1, j)와 (i+1, j+1) 중 더 큰 값과 현재 위치의 값을 더한 값으로 갱신됩니다.

2. 하위 문제의 결과 재활용:
   이미 계산한 하위 문제의 결과를 이용해 상위 문제를 해결합니다. 예를 들어, 하단에서 두 번째 층에서 경로를 계산할 때, 이미 하단에서 계산된 최대 경로 합을 사용합니다. 이렇게 하면 같은 경로를 여러 번 계산할 필요가 없습니다. 이처럼 DP는 중복 계산을 피하고, 이전에 계산한 결과를 재사용하기 때문에 효율성이 크게 증가합니다.

3. Bottom-Up 접근:
   이 코드에서는 DP를 하단에서 상단으로 올리는 Bottom-Up 방식으로 구현합니다. 먼저 삼각형의 하단(가장 작은 하위 문제)에서 시작하여, 점차적으로 상위 층으로 올라가면서 경로의 최대 합을 계산합니다. 최종적으로, 삼각형의 꼭대기에 위치한 값은 전체 삼각형의 최대 경로 합이 됩니다.

4. 최적 부분 구조(Optimal Substructure):
   동적 프로그래밍을 사용할 수 있는 문제는 최적 부분 구조(Optimal Substructure)를 가져야 합니다. 이는 전체 문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있다는 의미입니다.이 문제에서는 삼각형의 각 위치에서의 최적 경로가 그 하위 위치들의 최적 경로로부터 구해질 수 있으므로, 최적 부분 구조를 만족합니다.

// Top-Down 방식
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) {  // 왼쪽 끝이면
                    triangle[i][j] += triangle[i - 1][0];  // 이전 층의 0번째 값 더하기
                } else if (j == triangle[i].length - 1) {  // 오른쪽 끝이면
                    triangle[i][j] += triangle[i - 1][triangle[i - 1].length - 1];  // 이전 층의 -1번째 값 더하기
                } else {
                    triangle[i][j] += Math.max(triangle[i - 1][j], triangle[i - 1][j - 1]);
                }
            }
        }
        
        for (int num : triangle[triangle.length - 1]) {
            answer = Math.max(answer, num);
        }
        
        return answer;
    }
}