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

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

1932번: 정수 삼각형

문제 설명

• 크기가 N인 정수 삼각형 꼭대기에서 아래로 내려오면서 선택된 수의 합이 최대가 되는 경로 구하기
• 아래층 수는 현재층 대각선 왼쪽, 오른쪽만 선택 가능
• 삼각형의 크기는 1 이상 500 이하, 수는 0 이상 9999 이하의 정수

 

꼭 문제에 나와있는 그림처럼 정수 삼각형을 생각할 필요 없다. 

우선 DP[N+1][N+1] (dp [][] = 각 자리의 수) 배열을 만들어서 다음과 같이 초기화해주면 아래의 표처럼 배열이 완성된다.

dp [][1] 값들이 왼쪽 변이라고 생각하는 것이다.

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

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

 

꼭대기에서 아래로 내려올 때 대각선 왼쪽과 오른쪽 경로로만 갈 수 있으므로 배열 첫 번째 값(j=1)은 왼쪽 대각선으로만 가는 경우와 배열 마지막 값(j=i)은 오른쪽 대각선으로 가는 경우로 정해져 있다. 즉,

1. 맨 좌측일 경우

dp[i][j] += dp [i-1][1]

2. 맨 우측일 경우

dp [i][j] +=dp [i-1][j-1]

3. 그 외의 경우는 왼쪽 대각선과 오른쪽 대각선 값 중 큰 값을 더해주면 된다.

dp [i][j]+=Max(dp [i-1][j-1], dp [i-1][j])

 

import java.util.Scanner;

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