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

문제

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

코드

한 줄과 그 위의 줄만을 생각한 점화식을 세웠다.

0 0 0 0 0 0    ← i=0

0 7 0 0 0 0    ← i=1

0 3 8 0 0 0    ← i=2

0 8 1 0 0 0    ← i=3

0 2 7 4 4 0    ← i=4

0 4 5 2 6 5    ← i=5 == N

↑          ↑

j=0        j=5

 

입력값을 받는 배열이 triangle, 최대값이 들어가는 배열이 max_triangle이라 할 때,

max_triangle[i][j] 에 들어가는 배열을 생각하면

1) 윗 줄의 양 대각선 위치의 max_triangle 두 원소값 중 최대 → max(max_triangle[i-1][j-1], max_triangle[i-1][j])

2) triangle의 같은 위치 원소값 → triangle[i][j]

 

따라서 점화식은

D[i][j] = max(D[i-1][j-1], D[i-1][j]) + A[i][j]

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int[][] triangle = new int[N+1][N+1];
		int[][] max_triangle = new int[N+1][N+1];
		
		for(int i=1; i<=N; i++) {
			String[] str = br.readLine().split("\\s");
			for(int j=1; j<=str.length; j++) {
				triangle[i][j] = Integer.parseInt(str[j-1]);
			}
		}
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=i; j++) {
				max_triangle[i][j] = Math.max(max_triangle[i-1][j-1],max_triangle[i-1][j]) + triangle[i][j];
			}
		}
		
		int max = 0;
		for(int i=1; i<=N;i++) {
			max = Math.max(max, max_triangle[N][i]);
		}
		
		bw.write(Integer.toString(max));
		bw.flush();
	}
}