[백준(Baekjoon)][자바(java)] 1932 : 정수 삼각형 / 동적 계획법 1

 

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

1932번: 정수 삼각형

 

* 문제

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

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

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

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

 

* 풀이 방법

▶  이전 문제와 마찬가지로, 입력받은 2차원 배열에서 값을 더해가며 마지막 배열의 최댓값을 구함

  ( 배열을 따로 생성하지는 않음. 이전 문제와 같이, 입력된 값들의 누적 합을 구하는 문제이기 때문에 따로 값이 필요하지 않음 )

▶  각 층의 첫 번째 수는 오른쪽 위의 수(↑)와 더하면 됨

     각 층의 마지막 수는 왼쪽 위의 수(↖)와 더하면 됨

     각 층에서 첫 번째 수와 마지막 수를 제외한 수들은 오른쪽 위의 수(↑)와 왼쪽 위의 수(↖) 중 큰 것을 더해야 함

 

import java.util.Scanner;

public class Main {

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

 

import java.util.Scanner;

public class Main {

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