[Java]백준 1932번 정수삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

맨 위층부터 시작해 아래에 있는 수 중 하나를 선택하여 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 문제

풀이

---

위 그림으로 봤을때 경우의 수는 ABD, ABE, ACE, ACF가 될 수 있다

ABF나 ACE의 경우 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택하여야 하므로 될 수 없다.

 

D까지 더한 경우를 구하기 위해서는 A+B+D밖에 하지 못한다.

G의 경우에도 A+B+D+G로 D까지 더한 값에 G를 더한 값이 된다.

 

배열(i,j)로 볼 경우 (4,1) = (1,1)+(2,1)+(3,1)+(4,1)

즉, j=1로 고정이라면 list[i][j] = list[i-1][j-1] + list[i][j];

(4,4) = (1,1)+(2,2)+(3,3)+(4,4)의 경우

즉, i=j라면 list[i][j] = list[i-1][j-1] + list[i][j];

 

또한, 중간의 값 비교를 위해

(3,2) = (1,1)+(2,1)+(3,2) or (1,1)+(2,2)+(3,2) 두 가지 경우 비교를 위해

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

 

public class algo_1932_dp {
	static int[][] list;
	public static void main(String[] args) {
	        Scanner sc = new Scanner(System.in);
	        int n = sc.nextInt();
	        int sum = 0, tmp = 0;
	        list = new int[n + 1][n + 1];
	 
	        for (int i = 1; i <= n; i++) {
	            for (int j = 1; j <= i; j++) {
	                list[i][j] = sc.nextInt();
	 
	                if (j == 1)
	                    list[i][j] = list[i - 1][j] + list[i][j];
	                else if (j == i)
	                    list[i][j] = list[i - 1][j - 1] + list[i][j];
	                else
	                    list[i][j] = Math.max(list[i - 1][j - 1], list[i - 1][j]) + list[i][j];
	 
	                if (sum < list[i][j])
	                    sum = list[i][j];
	            }
	        }
	        System.out.println(sum);
	    }
}