[프로그래머스 알고리즘 고득점 kit] 동적계획법(Dynamic Programming) 정수 삼각형 - JAVA

🧐 문제

💡문제
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

<제한사항>
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
<입출력 예>
triangle : [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

프로그래머스

 

---

✅ 접근 방식

1️⃣ Top Down (시행착오)

문제에서 요구하듯이 위에서부터 아래로 차례로 숫자를 더해가며 최대의 숫자를 찾고자 하였다.

하지만 위에서 아래로 내려가며 최댓값을 찾는 방식은 바로 난관에 부딪혔다.

첫번째의 index는 7이 고정이고,

그 다음의 값의 선택지는 3 또는 8이다. 

하지만 우리는 최댓값을 구하는 것이 목표이기 때문에 자연스럽게 큰 값인 8을 선택하게 된다.

 

하지만 3번째의 index에 다다르게 되면 이야기가 달라진다.

3번째의 index에서는 최댓값인 1을 선택하게 된다 그러면 현재의 총합 값은 16이다.

하지만 실제로 3번째 인덱스까지의 최댓값은 7 + 3 + 8인 18이다.

 

그렇다면 어떻게 로직을 짤 수 있을까?

	int index = 0;
        for (int i = 3; i <= height; i ++){
            int a = Math.max(dp[i-2] + triangle[i-2][index] + triangle[i-1][index],
                             dp[i-2] + triangle[i-2][index] + triangle[i-1][index+1]);
            int b =  Math.max(dp[i-2] + triangle[i-2][index+1] + triangle[i-1][index+1], 
                              dp[i-2] + triangle[i-2][index+1] + triangle[i-1][index+2]);
            
            if (a < b){
                dp[i] = b;
                index ++;
            }else{
                dp[i] = a;
            }
            dp[i-1] = dp[i-2] + triangle[i-2][index];   
        }

첫번째로 생각했던 방식은 위의 코드와 같았다.

3개의 층을 모두 고려하여 가장 최대 값이 나온 경로를 찾아서 누적시키는 방식이다.

 

하지만 이러한 방식도 문제가 있었다

위와 같이 3개의 층대로 최댓값을 구하러 가는 경로와 다른 곳에 갑자기 큰 값이 나타날 때이다.

이러한 경우는 고려하지 못한다.

 

그렇다면 완전 탐색으로 모든 경로를 탐색하여 최댓값인 경로를 찾아야하는데,

이는 삼각형의 높이가 500인 경우에 시간초과가 뜰 확률이 매우 크다...

 

따라서 방법을 다르게 생각해야한다.

---

2️⃣ Bottom Up (정답)

위에서 아래로 진행하는 것과는 반대로 아래에서 위로 bottom up의 방식으로 접근하는 것이다.

bottom up을 생각하면 바로 dp가 떠오른다.

아래에서부터 한 층 한 층 올라가면서 2와 인접한 index중 더 큰 값을 더하여 dp 배열을 업데이트 해나가는 방법이다.

dp[i][j] = triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);

위와 같이 dp 배열도 triangle의 배열처럼 2차원 배열로 설정하고 각각의 배열값에는 아래의 두 값 중 최댓값 + 현재 index의 값을 더하면 계속해서 최댓값으로 업데이트할 수 있고 우리는 최종적으로 dp[0][0]을 반환하면 된다.

---

✅ 코드

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int height = triangle.length;
        int[][] dp = new int[height][height];

        // DP 배열 초기화 (맨 아래 줄 그대로 복사)
        for (int i = 0; i < height; i++) {
            dp[height-1][i] = triangle[height-1][i];
        }

        // Bottom-Up 방식으로 위로 올라가면서 최댓값 계산
        for (int i = height - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }

        return dp[0][0];
    }
}