🔍 Problem

1932 정수 삼각형

---

📃 Input&Output

---

📒 해결 과정

1.트리를 직삼각형 매트릭스로 그리기

	1	2	3	4	5
1	7
2	3	8
3	8	1	0
4	2	7	4	4
5	4	5	2	6	5

위의 2차원 매트릭스를 item이라고 명명하자.

2. 각 경로의 합을 DP값으로 정하여 매트릭스 그리기

	1	2	3	4	5
1	7
2	10	15
3	18	16	15
4	20	25	20	19
5	24	30	27	26	24

위의 매트릭스를 dp라고 명명하자.

위의 빨간색 16이 어떻게 나왔는지 살펴보자.

가. 대각 계산

Item

	1	2	3	4	5
1	7
2	3	8
3	8	1	0
4	2	7	4	4
5	4	5	2	6	5

DP

	1	2	3	4	5
1	7
2	10	15
3	18	11	0
4	0	0	0	0
5	0	0	0	0	0

위에서 11의 좌표는 (3,2)이고 이 값은
dp[3][2] = item[3][2]+ dp[2][1] 이다.

점화식
$dp[i+1][j+1] = item[i+1][j+1] + dp[i][j]$

나. 수직 계산
Item

	1	2	3	4	5
1	7
2	3	8
3	8	1	0
4	2	7	4	4
5	4	5	2	6	5

DP

	1	2	3	4	5
1	7
2	10	15
3	18	16	0
4	0	0	0	0
5	0	0	0	0	0

위에서 16의 좌표는 (3,2)이고 이 값은
dp[3][2] = item[3][2]+ dp[2][2] 이다.

점화식
$dp[i+1][[j] = item[i+1][j] + dp[i][j]$

다. dp 매트릭스가 채워지는 흐름 파악
dp 매트릭스는 위의 가,나 두과정을 모두 거쳐 채워진다. 그렇다면 위의 연산들을 모두 실행하되, 갱신을 할때, 갱신을 하는 dp값과 연산중 max값을 구하면 된다. 따라서 점화식은 다음과 같이 나온다.

점화식
1. $dp[i+1][j+1] = max(dp[i+1][j+1],item[i+1][j+1] + dp[i][j])$

2. $dp[i+1][j] = max(dp[i+1][j],item[i+1][j] + dp[i]j

위 점화식을 코드에 넣어 이중 for문 돌려 계산해주면 된다.

3. for문 범위구하기

dp 매트릭스를 채울 때의 좌표를 나열해보면 다음과 같다.

(1,1)
(2,1), (2,2)
(3,1), (3,2), (3,3)
...
(5,..)

따라서
$(i,j)일 때,$
$0\leq i \leq N-1$
$1\leq j \leq i$

---

❗트러블슈팅

1. dp[1][1]=item[1][1];

위 코드를 안넣어서 dp 매트릭스 연산이 꼬였었다.

항상 DP 처음 값을 초기화하는 것을 빼먹지 말자.

2. Index 6 out of bounds for length at P1932.mai

배열길이가 6짜리인데 인덱스가 0부터 5가능하지만 6으로 벗어났다는 의미이다.

for (int j = 1; i<=j; j++) {
                     
를
                     
for (int j = 1; j <= i; j++) {

로 수정

단순한 코드 실수 😥

---

💻 Code

import java.util.Scanner;

public class Main {
//public class P1932 {

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int max_val=0;
        int[][] item = new int[N+1][N+1];
        int[][] dp = new int[N+1][N+1];

        for (int i=1;i<=N;i++){
            for (int j =1;j<=i;j++){
                item[i][j] = sc.nextInt();
            }
        }

        dp[1][1]=item[1][1];


        for (int i=1;i<=N-1;i++) {
            for (int j = 1; j <= i; j++) {
                dp[i+1][j]=Math.max(dp[i+1][j],dp[i][j]+item[i+1][j]);
                dp[i+1][j+1]=Math.max(dp[i+1][j+1], dp[i][j]+item[i+1][j+1]);
            }
        }

        for (int i=1;i<=N;i++){
            max_val=Math.max(dp[N][i],max_val);
        }

        System.out.print(max_val);
    }
}

---

🤔 느낀점

DP 개념을 잡았을 때, 한번 이론으로 접한 문제라 풀 수 있었다. 그리고 DP 초기값을 초기화하는 것을 잊지말자.