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

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_1932 {

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

 

※ 내 생각
이 문제는 DP를 이용해서 문제를 해결할 수 있습니다.
아래의 그림과 같이 규칙을 찾을 수 있습니다.
각각의 위치에 dp의 배열에 누적 합을 계산해 주면 됩니다.
단. dp에 대해서 최댓값을 비교하면서 구해줘야 합니다.
즉, 3행 2열의 1의 경우는
7 + 3 + 1 과
7 + 8 + 1 에 대한 최댓값을 고민해야 합니다...