[백준 문제 풀기] 1932번: 정수 삼각형 (DP, 자바)

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

 

문제
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

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

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

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

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

 

예제 입력, 출력

	예제 입력	예제 출력
1	5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	30

 

사용 알고리즘

DP

 

코드 (자바)

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

// https://www.acmicpc.net/problem/1932
// 정수 삼각형



public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		
		int N = Integer.parseInt(st.nextToken());
		int[][] triangle = new int[N+1][N+1];		// 입력받은 삼각형
		
		// 입력받은 삼각형 저장
		for (int i=1 ; i<=N ; i++) {
			st = new StringTokenizer(br.readLine().trim());
			for (int j=1 ; j<=i ; j++) {
				triangle[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
//		System.out.println(Arrays.deepToString(triangle));
		
		// 로직 시작
		int[][] dp = new int[N+1][N+1];	// 경로에 따른 합계를 저장할 배열 선언
		int MAX = 0;					// 합계가 가장큰 구간합을 저장할 변수
		
		for (int i=1 ; i<N ; i++) {		// i 기준으로 다음 줄 까지 연산을 할꺼기 때문에 for 문은 N 직전까지만 돈다
			if (i==1) {
				dp[1][1] = triangle[1][1];
				MAX = dp[1][1];
			}
			
			
			for (int j=1 ; j<=i ; j++) {
				// 현재값 기준 왼쪽 숫자를 더했을 때
				if (dp[i+1][j] < triangle[i+1][j] + dp[i][j]) {
					dp[i+1][j] = triangle[i+1][j] + dp[i][j] ;
					if (dp[i+1][j] > MAX) { MAX = dp[i+1][j] ; }
				}
				
				// 현재값 기준 오른쪽 숫자를 더했을 때
				if (dp[i+1][j+1] < triangle[i+1][j+1] + dp[i][j]) {
					dp[i+1][j+1] = triangle[i+1][j+1] + dp[i][j] ;
					if (dp[i+1][j+1] > MAX) { MAX = dp[i+1][j+1] ; }
				}				
			}
		}
		
//		System.out.println(Arrays.deepToString(dp));
		System.out.println(MAX);
		
		
	}
	
}


/* [인터돌™] 공부 해보자!! 열심히~~~ http://globalhost.tistory.com */