[백준 1932] - 정수 삼각형(JAVA)

[문제]

출처 - https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

---

[문제 풀이]

위에부터 아래로 내려가면서 값을 더하며 최하단층에서 가장 최댓값을 구한다고 생각을 한다.

 

이 아이디어를 토대로 점화식을 d[i][j] = (i,j) 에 도착했을 때 합의 최댓값이라고 설정한다.

 

어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위, 오른쪽 위에 있는 것

즉 ( i , j )가 선택되기 전에 선택된 수는 왼쪽 위 ( i-1, j-1)  오른쪽 위 ( i-1, j )이고

 

D[i][j] = Max(D[i-1][j] , D[i-1][j-1] ) + A[i][j](현재 값)라고 표현할 수 있다.

 

최하단층에 최댓값을 모아두었기 때문에 마지막층에서 MAX값을 찾는 계산을 하면 문제의 정답을 찾을 수 있다.

 

---

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int d[][] = new int[n+1][n+1];
		int a[][] = new int[n+1][n+1];
		
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1; j<=i; j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				d[i][j] = Math.max(d[i-1][j-1], d[i-1][j]) + a[i][j];
			}
		}
		int ans=0;
		//마지막층 각각에 최댓값을 가지고 있어서 가장 큰 값 찾아준다.
		for(int i=1; i<=n; i++) {
			if(ans < d[n][i]) ans = d[n][i]; 
		}
		
		System.out.println(ans);
	}
}