백준 동적계획법 - 1932번 : 정수 삼각형

 

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

1932번: 정수 삼각형

---

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


public class Main {
		public static int[][] memo;
		public static int[][] tri;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		tri = new int[n][n];
		memo = new int[n][n];
		int num = 1;
		for(int i=0; i<n; i++) {
			Arrays.fill(tri[i],-1);
			Arrays.fill(memo[i],-1);
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<num; j++) {
				tri[i][j] = Integer.parseInt(st.nextToken());
			}
			num++;
		}
		memo[0][0] = tri[0][0];
		for(int i=1; i<n; i++) {
			for(int j = 0; j<=i; j++) {
				if(j==0) {
					memo[i][j] = tri[i][j] + memo[i-1][0];
				}
				else if(j==i) {
					memo[i][j] = tri[i][j] + memo[i-1][i-1];
				}
				else {
					memo[i][j] = tri[i][j] + Math.max(memo[i-1][j],memo[i-1][j-1]);
				}
			}	
		}
		int max = -1;
		for(int i=0; i<n; i++) {
			if(max<memo[n-1][i]) {
				max = memo[n-1][i];
			}
		}
		bw.write(max+"");
		bw.close();
	}
}