[백준] 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번째 줄까지 정수 삼각형이 주어진다.

출력 >

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

 

해결방법 > 

동적 계획법으로 해결

 

7

3 8

8 1 0

2 7 4 4 

4 5 2 6 5

 

위의 삼각형이 있을 때 밑에서부터 경로를 찾아나간다.

i행의 j번째까지의 총 이동거리는 (i+1)행의 j번째와 (j+1)번째 경로까지의 최대값 + i번째 j번째의 거리이다.

 

S[i][j] = max(D[i+1][j], D[i+1][j+1]) + D[i][j]; 

(D[i][j] : 경로의 이동거리    S[i][j] : 총 이동거리)

 

7

3 8

8 1 0

2 7 4 4  <- 시작점

4 5 2 6 5

------------------

7

3 8

8 1 0

7 12 10 10

------------------

7

3 8

20 13 10

------------------

7

23 21

------------------

30

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_1932 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] a = new int[n + 1][n + 1];
		int[][] s = new int[n + 1][n + 1];
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j <= i; j++) {
				a[i][j] = sc.nextInt();
				
				if(i == n-1) {
					s[i][j] = a[i][j];
				}
			}
		}
		
		for(int i = n-2; i >= 0; i--) {
			for(int j = 0; j <= i; j++) {
				s[i][j] = Math.max(s[i+1][j], s[i+1][j+1]) + a[i][j];
			}
			for(int j = 0; j <= i; j++) {
				System.out.print(s[i][j] + " ");
			}
			System.out.println();
		}
		
		System.out.println(s[0][0]);
	}
}

 

문제링크 >

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

1932번: 정수 삼각형