백준 1932 정수 삼각형

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

문제해결

구하고자 하는 것은 합이 최대가 되는 경로에 있는 수의 합이다. 문제를 처음 봤을 때 점화식을 어떻게 세워야 할 지 감이 오지 않아서 다른 사람 풀이를 참고했다.

먼저 입력으로 받은 값을 i번째 행, j번째 열 형식으로 2차원 배열에 넣어주었다. 이에 따라 점화식은 D[i][j] = i행 j열을 선택했을 때 합이 최대가 되는 경우가 된다. 초기값은 제일 위에 있는 값으로 정의하였으며, 기준을 다음 행, 다음 열로 잡고 풀이를 진행하였다.

주어진 예제를 보면 초기값은 첫 번째 행, 첫 번째 열인 dp[0][0] = arr[0][0]으로 7이 된다. 다음으로 2차원 배열의 인덱스를 집중해서 보자. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 오른쪽에 있는 것 중에서만 선택 가능하다고 한다. 이전 층의 인덱스와 삼각형의 왼쪽에 위치한 값의 인덱스를 비교했을 때 (i-1, j)이며 오른쪽에 위치한 값의 인덱스는 (i-1, j-1)이 된다.
여기서 i+1이 아니라 i-1인 이유는 앞에서 현재 층의 기준을 다음 행, 다음 열로 잡았기 때문이다.

이와 같은 방법으로 첫 번째 열에 위치한 경우 이전 행까지 누적된 값 + 자신의 값이 되고, 두 번째 열부터 ~ N번째 열에 위치한 경우 이전 행까지의 누적된 값 중 최댓값 + 자신의 값이 된다.
글로 표현하자니 무슨 소리인가 싶겠지만 코드를 보면 금방 이해될 것이다.

소스코드

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

public class b1932 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n][n];
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp[0][0] = arr[0][0]; // 제일 위에 값
        for (int i = 1; i < n; i++) { // 행
            for (int j = 0; j <= i; j++) { // 열
                dp[i][j] = dp[i - 1][j] + arr[i][j];
                // 두 번째 ~ N번째 열일 경우
                if (j - 1 >= 0 && dp[i][j] < dp[i - 1][j - 1]+arr[i][j]) {
                    dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
                }
            }
        }
        int ans = dp[n - 1][0];
        for (int i = 0; i < n; i++) {
            if (ans < dp[n - 1][i]) {
                ans = dp[n - 1][i]; // 최댓값 출력
            }
        }
        System.out.println(ans);
    }
}

넘나 어려운 DP 문제,, 혼자 힘으로 풀 수 있는 문제가 있긴할까,,