[백준] 1932번: 정수 삼각형(DP, 동적계획법)

백준 1932번 - 정수 삼각형(DP)

 

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

1932번: 정수 삼각형

코드

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

public class Main {

	// n층에 있는 경로중 최댓값 찾기
	public static int findMax(int n, int[][] arr) {
		int max = 0;
		for(int i=0; i<n; i++) 
			if(arr[n-1][i] > max)
				max = arr[n-1][i];
		return max;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		Scanner scan = new Scanner(System.in);

		int n = Integer.parseInt(bf.readLine());
		int[][] dp = new int[n][n];
		StringTokenizer st;

		// 층별로 정수 입력받기
		for(int i=0; i<n; i++) { 
			st = new StringTokenizer(bf.readLine());
			for(int j=0; j<=i; j++) {
				dp[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for(int i=1; i<n; i++) {
			for(int j=0; j<=i; j++) {
				// 층별로 젤 왼쪽일 때
				//  -> 바로 윗층(dp[i-1][j]) 과 그 층(dp[i][j])의 합 1가지밖에 없음.
				if(j == 0)
					dp[i][j] = dp[i-1][j] + dp[i][j];

				// 층별로 젤 오른쪽일 때
				//  -> 바로 윗층(dp[i-1][j-1]) 과 그 층(dp[i][j])의 합 1가지밖에 없음.
				else if(j == i)
					dp[i][j] = dp[i-1][j-1] + dp[i][j];
				
				// 층별로 맨왼쪽, 맨오른쪽이 아닌 중간일때
				//  -> 대각선 왼쪽위 / 대각선 오른쪽위와의 합 중 큰 값 
				else 
					dp[i][j] = Math.max(dp[i-1][j-1] + dp[i][j], dp[i-1][j] + dp[i][j]);
			}
		}

		System.out.println(findMax(n, dp));
		bf.close();
	}

}

풀이

문제에서 나온 5층을 기준으로 보자.

 * 첫 층은 배열의 인덱스 시작에 따라 0층으로 해서 0, 1, 2, 3, 4층으로 판단함.

가장 왼쪽의 값(7, 3, 8, 2, 4)는 선택할 수 있는 경우가 1가지 밖에 없다.(아래사진)

따라서 층마다 j가 0일때는 바로 윗층값 + 현재층값을 더해준다.

1층 -> 7 + 3

2층 -> 7 + 3 + 8

3층 -> 7 + 3 + 8 + 2

4층 -> 7 + 3 + 8 + 2 + 4

if(j == 0)
    dp[i][j] = dp[i-1][j] + dp[i][j];

 

층마다 j가 i일때(가장 오른쪽값)도 마찬가지로 선택할 수 있는 경우가 1가지 밖에 없다.

따라서 층마다 j가 i일때는 대각선왼쪽위에 값 + 현재층 값을 더해준다.

1층 -> 7 + 8

2층 -> 7 + 8 + 0

3층 -> 7 + 8 + 0 + 4

4층 -> 7 + 8 + 0 + 4 + 5

else if(j == i)
    dp[i][j] = dp[i-1][j-1] + dp[i][j];

 

마지막으로 j가 가장 왼쪽도 아니고 가장 오른쪽도 아닌 중간값들일때

왼쪽 대각선위와 오른쪽 대각선위와의 합 중 큰값을 구해주면 된다.

else 
    dp[i][j] = Math.max(dp[i-1][j-1] + dp[i][j], dp[i-1][j] + dp[i][j]);

 

위 반복문이 n층까지 끝나면,

n층의 각 값들은 해당 층으로 존재하는 값 중 최댓값이 된다.

(4,3) 의 6이라는 값 까지 더하려면

(3,2) OR (3,3)의 값 까지 더한 것중 큰 값과 합을 구해야 한다.

 

5층을 기준으로 각 과정을 살펴보면 아래와 같다.