[Baekjoon 1932] 정수 삼각형 - JAVA

[Silver I] 정수 삼각형 - 1932

문제 링크

성능 요약

메모리: 27212 KB, 시간: 296 ms

분류

다이나믹 프로그래밍

문제 설명

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

출력

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

문제풀이

DP 문제이기 때문에 점화식이 중요하다.

점화식은 d[i][j] = Math.max(d[i - 1][j - 1], d[i - 1][j]) + a[i][j]이다.

점화식을 구하는 과정은 아래와 같다.

여기서 d[i][j]는 i번째 행의 j번째 열까지의 경로 중 선택된 수의 합의 최댓값을 나타낸다. a 배열은 입력으로 주어진 정수 삼각형을 저장한 배열이며, d 배열은 최댓값을 저장하기 위한 배열이다.

이 점화식은 현재 위치 (i, j)에서 이전 행의 대각선 왼쪽 값 d[i-1][j-1]와 대각선 오른쪽 값 d[i-1][j] 중에서 큰 값을 선택하고, 현재 위치의 숫자 a[i][j]를 더한 것을 d[i][j]로 설정한다. 이를 통해 각 위치까지의 최댓값을 계산할 수 있다.

문제에서는 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 따라서 현재 위치 (i, j)에 도달하기 위해서는 이전 행의 대각선 왼쪽 값 d[i-1][j-1] 또는 대각선 오른쪽 값 d[i-1][j] 중 더 큰 값을 선택해야 한다.

즉, (i, j) 위치까지의 최댓값은 바로 위의 두 값 중 큰 값에 현재 위치의 숫자 a[i][j]를 더한 것이다. 이를 계속해서 각 위치마다 반복하면 최종적으로 맨 아래층까지 도달했을 때의 최댓값을 구할 수 있다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

		int d[][] = new int[n + 1][n + 1];
		int a[][] = new int[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= i; j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = Math.max(d[i - 1][j - 1], d[i - 1][j]) + a[i][j];
			}
		}

		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (ans < d[n][i]) ans = d[n][i];
		}

		System.out.println(ans);
	}
}

코드 풀이

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

int d[][] = new int[n + 1][n + 1];
int a[][] = new int[n + 1][n + 1];

입력을 저장할 변수 n을 만들어준다.

d는 경로의 최댓값을 저장하기 위한 배열이고, a는 주어진 삼각형 배열의 값을 저장하기 위한 배열이다.

for (int i = 1; i <= n; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 1; j <= i; j++) {
        a[i][j] = Integer.parseInt(st.nextToken());
    }
}

i가 현재 삼각형의 열 번호를 나타내는 for문이다.

j가 현재 삼각형의 열 번호를 나타내는 for문이다.

이전 단계를 통해 주어진 삼각형 배열의 값들이 a 배열에 저장한다.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        d[i][j] = Math.max(d[i - 1][j - 1], d[i - 1][j]) + a[i][j];
    }
}

i가 현재 삼각형의 행 번호를 나타내는 for문이다.

j가 현재 삼각형의 행 번호를 나타내는 for문이다.

현재 위치인 d[i][j]에 이전 행에서 선택 가능한 경로 중 최댓값을 선택하고, 현재 위치의 값 a[i][j]를 더해 저장해서 현재 위치까지의 최댓값으로 바꿔준다.

int ans = 0;
for (int i = 1; i <= n; i++) {
    if (ans < d[n][i]) ans = d[n][i];
}

최종적으로 출력할 최댓값을 저장할 ans 변수를 0으로 초기화해서 생성한다.

i가 현재 삼각형의 열 번호를 나타내는 for문이다.

d[n][i]는 마지막 행에서 각 열까지의 경로 중 최댓값이다. 현재까지의 최댓값 ans보다 d[n][i]가 더 크다면, ans 값을 d[n][i]로 바꿔준다.

최종적으로 구한 최댓값 ans를 출력한다.