백준 1932 - 정수 삼각형

Java

1932 번 - 정수 삼각형

문제

접근 방법

dp 사용하여 해결하였다.
2번째 줄 피라미드 부터, 자신의 위 2개 중 큰 dp를 계속하여 가져오면서 최댓값을 구하였다.
최종적으로 가장 아래 n번째 줄에서 가장 큰 값이 곧 최대가 되는 경로에 있는 수의 합이 된다.

코드

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

public class Main {
	static int n, result;
	static int[][] pira;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	pira = new int[n][n];

    	for(int i = 1; i <= n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < i; j++) {
    			pira[i - 1][j] = stoi(stk.nextToken());
    		}
    	}

    	int[][] dp = new int[n][n];

    	dp[0][0] = pira[0][0];
    	for(int i = 1; i < n; i++) {
    		for(int j = 0; j < i + 1; j++) {
				// 현재 줄의 제일 왼쪽
    			if(j == 0)
    				dp[i][j] = dp[i - 1][j] + pira[i][j];
				// 현재 줄의 제일 오른 쪽
    			else if(j == i)
    				dp[i][j] = dp[i - 1][j - 1] + pira[i][j];
				// 나머지 중간 지점에서는 점화식을 이용
    			else
    				dp[i][j] = Math.max(dp[i - 1][j] + pira[i][j], dp[i - 1][j - 1] + pira[i][j]);

    		}
    	}

    	for(int i = 0; i < n; i++) {
    		result = Math.max(result, dp[n - 1][i]);
    	}
    	System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

간단한 DP 문제

개선할 점