[백준 1932번 : 실버1] 정수 삼각형 ( DP / Java )

이번 문제는 DP 문제에서 약간의 응용이 섞인것 같았다.

하지만 기본적인 DP를 알고 있다면 충분히 풀수 있는 문제 같다.

 

 

문제를 살펴보자.

 

 

 

문제

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

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

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

입력

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

출력

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

 

 

 

 

 

문제 접근 방법

일단 이번 문제는 최상단에는 제일 큰값이 있어야 한다.

따라서 누적으로 최대값을 구해야 한다.

 

그럼 우리가 각각의 index의 값은 어떻게 최대값을 가지게 될까를 생각해봐야 한다.

 

문제에서 내준 조건은 아래와 같다.

 

선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택

 

아래와 같이 삼각형이 그려진다 했을때 

 

0

01

012

0123

01234

 

0에서 선택할수 있는 수는 0,1이고1에서 선택할수 있는 수는 1,22에서 선택할수 있는 수는 2,33에서 선택할수 있는 수는 3,4 이다.

 

이로써 우리는 특정 index에서 index, index+1 일중 숫자가 큰것을 고르면 된다.

 

따라서 위 방식은 두개의 수중 큰것을 선택하게 되기때문에 식은 아래와 같이 만들어진다.

Math.max(findMax(dp,triangle,height+1,index), findMax(dp,triangle,height+1,index+1))

 

그럼 이제 우리가 할일은 초기값을 설정하는 일이다.

우리가 초기값을 설정할 필요가 없는 부분은 제일 아래 층에 있는 숫자들이다.

따라서 나는 아래와 같이 숫자들을 아래와 같이 저장한후에

저장되어 있는 숫자들을 위의 점화식을 활용해서 문제를 풀었다.

 

-1

-1-1

-1-1-1

-1-1-1-1

4 5 2 6 5 

 

그럼 이제 소스를 보면 소스가 무슨 말을 하는지 이해가 갈것이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Run {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Run a = new Run();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int height = Integer.parseInt(br.readLine());

		ArrayList<Integer>[] triangle = new ArrayList[height];
		ArrayList<Integer>[] dp = new ArrayList[height];

		for (int i = 0; i < height; i++) {
			triangle[i] = new ArrayList<Integer>();
			dp[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < height; i++) {
			String[] su = br.readLine().split(" ");

			for (int j = 0; j < su.length; j++) {
				triangle[i].add(Integer.parseInt(su[j]));
				if(i == height-1)
					dp[i].add(Integer.parseInt(su[j]));
				else
					dp[i].add(-1);
			}
		}

		System.out.println(a.findMax(dp, triangle, 0,0));

	}

	public int findMax(ArrayList<Integer>[] dp, ArrayList<Integer>[] triangle, int height, int index) {
		// TODO Auto-generated method stub
		
		if(dp[height].get(index) == -1) { //해당 부분의 값이 -1이라면 진입
			int max = Math.max(findMax(dp,triangle,height+1,index), findMax(dp,triangle,height+1,index+1)) + triangle[height].get(index);
			dp[height].set(index, max);
		}
		
		return dp[height].get(index);
	}
}

 

 

 

느낀점

1. 어떤걸 선택해야하는지를 잘 생각해서 점화식을 만들자.