[백준] 1932: 정수 삼각형

'1932- 정수 삼각형' 문제로 이동!

👉문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

👉입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

예시 -
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

👉출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예시 - 30

---

✍내 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[][] triangle = new int[num+1][num+1];
		for( int i = 1 ; i <= num ; i++) {
			for( int j = 1 ; j <=i ; j++) {
				triangle[i][j] = sc.nextInt();
			}
		}
		System.out.println(maxTriangle(triangle, num));
	}
	
	static long maxTriangle( int[][] triangle, int n ) {
		long[][] memo = new long[n+1][n+1];
		memo[1][1] = triangle[1][1];
		for( int i = 2 ; i <= n ; i++) {
			for( int j = 1 ; j <= i ; j++) {
				memo[i][j] = Math.max(memo[i-1][j-1], memo[i-1][j]) + triangle[i][j];				
			}
		}
		
		long max = 0;
		for( int i = 1 ; i <= n ; i++) {
			if( max < memo[n][i]) max = memo[n][i];
		}
		return max;
	}
	
}

---

✍점화식

memorizing하는 배열 : 해당 자리의 숫자까지 더해지는 최대의 합을 저장함

배열로 따졌을 때 triangle[i][j]는 memo[i-1][j-1]와 memo[i-1][j]중 큰 값과 더해져 memo[i][j]에 저장된다.
( 문제에서 말하는 대각선 왼쪽 또는 대각선 오른쪽이 j-1와 j에 해당하는 값이다. )
즉 다음과 같은 코드를 말한다.

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

---

✍Note

이전까지 memorizing해놓은 값과 해당 자리의 값을 더하는 구조!
1149:RGB거리 문제 와 유사한 문제이다.
( 풀이 : RGB거리 문제 풀이 링크 )