[백준/1932/Java] 정수 삼각형

 

문제링크:

www.acmicpc.net/problem/1932

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번째 줄까지 정수 삼각형이 주어진다.

 

출력

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

 

 

풀이

먼저 점화식을 구하기 위하여 문제에 있는 샘플에서 2번째 줄과 3번째 줄을 가져와서 분석을 해보도록 하겠습니다.

 

<그림1> 2층과 3층 데이터

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다고 하였습니다.

문제에서 합이 최대가 되는 경로라고 하였으므로 아래층으로 이동하면서 현재까지의 합을 구하는데 가장 큰 값을 구하면 됩니다.

 

 

배열 형태로 표현하면 i, j는 이렇게 됩니다

<그림2> D[3][1] 합

 

합을 구하는 배열 이름을 D라고 하겠습니다.

위 그림에서 노란색으로 표시한 D[3][1] 를 구하려면 2층에 있는 대각선 왼쪽, 대각선 오른쪽에 있는 수를 더해야 합니다.

이 2가지 경우를 보도록 하겠습니다.

 

1) 대각선 왼쪽에 수가 존재하지 않습니다. (위 그림1 참고)

따라서, D[3][1] = 대각선 왼쪽(0) + 8 입니다.

 

2) 대각선 오른쪽에 D[2][1]이 존재합니다.

따라서, D[3][1] = D[2][1] + 8 = 3 + 8 = 11입니다.

 

2번의 경우가 11로 더 크므로 D[3][1]에 11을 저장합니다.

 

 

<그림3> D[3][2] 합

위 그림에서 노란색으로 표시한 D[3][2] 를 구하려면 2층에 있는 대각선 왼쪽, 대각선 오른쪽에 있는 수를 더해야 합니다.

이 2가지 경우를 보도록 하겠습니다.

 

1) 대각선 왼쪽에 D[2][1]이 존재합니다.

따라서, D[3][2] = D[2][1] + 1 = 3 + 1 = 4입니다.

 

2) 대각선 오른쪽에 D[2][2]이 존재합니다.

따라서, D[3][2] = D[2][2] + 1 = 8 + 1 = 9입니다.

 

2번의 경우가 9로 더 크므로 D[3][2]에 9를 저장합니다.

 

점화식

1번의 점화식은 D[i][j] = D[i-1][j-1] + 현재값이고

2번의 점화식은 D[i][j] = D[i-1][j] + 현재값이라는 것을 알 수 있습니다.

 

 

<그림4> D[3][3] 합

위 그림에서 노란색으로 표시한 D[3][3] 를 구하려면 2층에 있는 대각선 왼쪽, 대각선 오른쪽에 있는 수를 더해야 합니다.

이 2가지 경우를 보도록 하겠습니다.

 

1) 대각선 왼쪽에 D[2][2]이 존재합니다.

따라서, D[3][3] = D[2][2] + 0 = 8 + 0 = 8입니다.

 

2) 대각선 오른쪽에 수가 존재하지 않습니다.

따라서, D[3][3] = 대각선 왼쪽(0) + 0 = 0 입니다.

 

1번의 경우가 8로 더 크므로 D[3][3]에 8을 저장합니다.

 

 

수가 존재하는 경우를 살펴보도록 하겠습니다.

그림2에서 1번의 경우는 대각선 왼쪽에 수가 존재하지 않습니다.

1번 점화식은 D[i][j] = D[i-1][j-1] + 현재값인데 D[3][1] = D[2][0] + 현재값이므로 D[2][0]에 0을 저장하면 점화식에 문제가 없음을 알 수 있습니다.

 

그림4에서 2번의 경우는 대각선 오른족에 수가 존재하지 않습니다.

2번 점화식은 D[i][j] = D[i-1][j] + 현재값인데 D[3][3] = D[2][3] + 현재값이므로 D[2][3]에 0을 저장하면 점화식에 문제가 없음을 알 수 있습니다.

 

점화식 정리

점화식을 정리하면 큰 값을 저장하면 되므로 1번, 2번 점화식을 합쳐서

1번) D[i][j] = D[i-1][j-1] + 현재값

2번) D[i][j] = D[i-1][j] + 현재값

최종) D[i][j] = max(D[i-1][j-1], D[i-1][j]) + 현재값 입니다.

 

 

소스

현재값은 A 배열에 저장하고 합은 D 배열에 저장했습니다.

 

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

public class Main
{
	static int N;
	static int A[][];
	static int D[][];
	
	static int Answer;

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력
		N = Integer.valueOf(br.readLine());
		A = new int[N+1][N+1];
		D = new int[N+1][N+1];

		String input = null;
		StringTokenizer st = null;
		for (int i = 1; i <= N; i++)
		{
			input = br.readLine();
			st = new StringTokenizer(input);
			
			for (int j = 1; j <= i; j++)
			{
				A[i][j] = Integer.valueOf(st.nextToken());
			}
		}
		
		// 처리
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= i; j++)
			{
				D[i][j] = Math.max(D[i-1][j-1], D[i-1][j]) + A[i][j];
			}
		}
		
		// 출력
		for (int j = 1; j <= N; j++)
		{
			Answer = Math.max(Answer, D[N][j]);
		}
		System.out.println(Answer);
		
		// D배열 검증
//		for (int i = 1; i <= N; i++)
//		{
//			System.out.println(Arrays.toString(D[i]));
//		}
	}
}