[백준] 자바 1932 정수 삼각형

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

테스트 케이스

 

 

접근

dp문제이므로 최대한 쪼개서 생각해보려 노력하였습니다.

이중 배열을 사용하여 값들을 배열에 다 입력하고

배열의 최하단에서부터 계산을 시작합니다.

 

1번을 계산하고 2번을 계산한 후 상위 배열에 넣어줍니다 이 과정을 연속해서 하면 [0][0]이 최댓값을 가지게 됩니다.

 

코드

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

public class Main {

	/*
 	1932 problem 정수 삼각형
	위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
	맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
	삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
	*/

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		int dp[][] = new int[num][num];
		int tokenSize = 0;
		//배열에 값 넣는 for문
		for(int i=0; i<num; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			tokenSize = st.countTokens();
			for(int j=0; j<tokenSize; j++) {
				dp[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		//최대값을 계산해서 배열을 밑에서 부터 다시채움
		for(int i=num-1; i>0; i--) {
			for(int j=0; j<num-1; j++) {
				dp[i-1][j] = Math.max(dp[i][j] + dp[i-1][j], dp[i][j+1] + dp[i-1][j]);
			}
		}
		//[0][0]이 항상 최대값
		System.out.println(dp[0][0]);
		
		bw.flush();
		bw.close();
	}
}