[프로그래머스] (Java) 정수삼각형 (동적계획법/Dynamic Programming)

 

 

📑 1. 문제설명

---

💡 2. 접근방식

 
풀이방법
1. dp[][] 배열 선언
2. 첫 번째 줄 값 채우기 (dp[0][0] = triangle[0][0])
2. 왼쪽 첫번째 열인 dp[i][0] 값은 이전 줄의 첫 번째 값끼리 더해서 입력한다. (dp[i][0] = dp[i-1][0] + triangle[i][0])
3. 그 외의 값들은 위쪽과 왼쪽에서 오는 값을 비교하여 최대값을 더하기
(dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j])
즉, 위쪽에서 오거나 왼쪽 위에서 온 값 중 더 큰 값에 현재 triangle[i][j] 값을 더한다. 

---

 

dp[][] 배열 선언

나처럼 수학을 어려워하는 사람들을 위해 배열을 눈으로 보기 쉽게 시각화 해 보았다.
코드의 흐름에 따라서 순서대로 triangle[][] 배열, dp[][] 배열의 변화를  표 형식으로 나타내려고 한다. 

 

먼저 문제에서 주어진 triangle[][]을 그림으로 나타내면 위와 같고, 이것을 배열로 전환한 모습이 아래와 같다.
배열에서 굳이 쓰이지 않는칸은 검은색으로 표시했으나 원칙적으로는 int[][] 배열 선언시기본값이 0으로 초기화 된다. 

 
그리고 아래는 거쳐간 숫자의 합을 저장할 dp[][] 배열의 초기 상태이다.  

 

2-1.  첫 번째 단계: 첫 번째 줄 값 채우기 (dp[0][0] = triangle[0][0])

 

2-2. 두 번째 단계: dp 배열에 값 채우기 (dp[i][0] = dp[i-1][0] + triangle[i][0])

이제 여기서부터 값을 채울 때는 두 가지 경우로 나뉘게 된다. 
첫번째 열과, 나머지 칸을 채우는 점화식이 다르다.
 
먼저, 첫번째 열인 dp[i][0] 값은 이전 줄의 첫 번째 값을 더해서 구한다. (dp[i][0] = dp[i-1][0] + triangle[i][0])
왜 그러는지 그림으로 설명하자면 아래와 같다.

 
이것을 수행하는 점화식은 dp[i][0] = dp[i-1][0] + triangle[i][0] 인데 이 점화식의 의미를 아주 쉽게 설명 해 보자면 

👉 현재 위치 (dp[i][0])의 값 = dp배열에서 바로 윗칸에 있는 값 (dp[i-1][0]) +  현재 삼각형 값 (triangle[i][0])을 더한 것이다.

• dp[i-1][0]: 바로 위 칸의 값 (윗줄에서 내려온 값)
• triangle[i][0]: 현재 삼각형의 값
• dp[i][0]: 위에서 내려온 값과 현재 값을 더한 값

왜냐하면 맨 왼쪽 열(j == 0)은 왼쪽에서 오는 값이 없고 오로지 위에서 내려오는 값만 존재하기 때문에, 각 줄에서 위에 있던 값에 현재 칸의 값을 더해주면 된다.
 
그림으로 표현하면 아래와 같은 과정이 이루어진다. 

---

---

---

 
여기까지 수행한 후 dp[][] 배열의 상태는 아래와 같다. 

 

2-3. 세 번째 단계: 위쪽과 왼쪽에서 오는 값을 비교하여 최대값을 더하기

지금까지 dp[i][0] 값은 이전 줄의 첫 번째 값을 더해서 구한고 했다. 즉, 왼쪽 끝 값은 오직 위에서 내려오는 값만 고려하면 되므로 다음과 같은 점화식을 사용한다고 했다. (dp[i][0] = dp[i-1][0] + triangle[i][0]) 이 단계는 그 외 값인 중간에 있는 값을 구하기 위한 점화식이다. 
 
중간에 위치한 값들은 위에서 내려오는 `두 가지 경로`가 존재한다. 따라서 지나쳐온 경로의 합이 더 큰 값을 선택하여 저장해야 한다. 즉, 그 외의 값들은 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] 점화식으로 위쪽에서 오거나 왼쪽 위에서 온 값 중 더 큰 값에 현재 triangle[i][j] 값을 더한다.
 
즉, dp[i][j] 값은  두 가지 경로 중 더 큰 값을 선택하고, 현재 위치의 값을 더하여 최적의 경로를 만든다. 이 방식으로 마지막 줄에서 가장 큰 값을 찾으면, 삼각형을 타고 내려오는 최댓값을 구할 수 있다.
 

---

 

---

최종 dp[][] 배열에서 맨 아랫줄의 최댓값인 30 을 결과값으로 리턴한다. 
 

---

👨‍💻 3. 정답코드

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int height = triangle.length; // 삼각형의 높이
        int[][] dp = new int[height][height]; // 합을 저장할 DP 배열

        // 1. 첫 번째 줄 (맨 꼭대기 값)
        dp[0][0] = triangle[0][0];

        // 2. 첫 번째 열 채우기 (맨 왼쪽 경로)
        for (int i = 1; i < height; i++) {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
        }

        // 3. DP 배열 채우기 (왼쪽 위, 위쪽 비교)
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < triangle[i].length; j++) {
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] ;
            }
        }

        // 4. 최댓값 찾기 (마지막 행에서 최댓값)
        int answer = 0;
        for (int i = 0; i < height; i++) {
            answer = Math.max(answer, dp[height - 1][i]);
        }

        return answer;
    }
}

 

🐦 4. TMI

쉬고싶오 ㅋㅋㅋ
풀고 어떻게 설명할지 생각하고
자료만들고 포스팅하는데 3시간 걸렸옹
수학을 모탱