BOJ01932 정수 삼각형

https://www.acmicpc.net/problem/1932 (opens new window)

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

매번 내려올 때 마다 수를 비교하여 더 큰 것을 중간 결과로 저장해가며 최댓값을 찾기 위한 DP 문제이다.

제출 코드

삼각형의 끝쪽에 있는 index를 주의해서 사용해야 한다. 0 index와 반대쪽 마지막 index는 항상 정해진 이전 결과에서 합산을 진행하도록 한다.

for (int j = 0; j <= i; j++) {

    if (j == 0) {
        dp[i][j] = dp[i - 1][j] + Integer.parseInt(input[j]);
    } else if (j == i) {
        dp[i][j] = dp[i - 1][j - 1] + Integer.parseInt(input[j]);
    } else {
        dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + Integer.parseInt(input[j]);
    }
}

아래는 최종 제출 코드이다.

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

public class BOJ1932 {

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

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

        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] input = bufferedReader.readLine().split(" ");

            if (i == 0) {
                dp[0][0] = Integer.parseInt(input[0]);
                continue;
            }

            for (int j = 0; j <= i; j++) {

                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + Integer.parseInt(input[j]);
                } else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + Integer.parseInt(input[j]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + Integer.parseInt(input[j]);
                }
            }
        }

        int max = Arrays.stream(dp[n - 1]).max().getAsInt();
        System.out.println(max);
    }
}

#algorithm #BOJ #다이나믹 프로그래밍