백준_1932 정수 삼각형(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력

DP를 이용한 풀이

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Back_1932 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < i+1; j++) {
				map[i][j]= Integer.parseInt(st.nextToken());
			}
		}	
		
		int temp=0;
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < i+1; j++) {
				if(j==0) {
					map[i][j]+=map[i-1][j];
				}else if(i==j) {
					map[i][j]+=map[i-1][j-1];
				}
				else {
					map[i][j]+=Math.max(map[i-1][j-1], map[i-1][j]);
				}
				temp = Math.max(temp, map[i][j]);
			}
		}
		System.out.println(temp);
	}

}

- DP를 이용해서 문제를 풀 수 있습니다.

 

- 이 문제의 점화식을 구하는 방법은

 

- 맨 양 끝과 그 사이에 있는 것을 나눠서 점화식을 짜면 쉽게 짤 수 있습니다.