DP. 정수 삼각형

문제

단순한 1,2,3,4, ... , N N줄에 N개의 수가있는 유사 트리 형태의 문제. 줄을 따라 내려가면서 가장 큰값이 되는 값을 리턴한다.

해결방향성

일단 행, 열 중 열 == 1 -> 계속 1이랑만 더함
열 == N -> 계속 N - 1이랑만 더함
그 사이의 수는 더 큰 쪽을 따라간다.
사실, 이차원 배열을 이용하면 범위가 넘어가는 쪽은 0이므로 공통분모로 묶을 수있다.
즉, dp[i][k] = max (dp[i - 1][k - 1], dp[i - 1][k]) + num[i][k]

코드

package dp;

import java.io.*;
import java.util.StringTokenizer;

import static java.lang.Math.*;

public class IntegerTriangle {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int[][] num = new int[N + 1][N + 1]; // 1부터 N까지 사용
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                num[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num[i][j];
            }
        }

        int result = 0;

        for (int i = 1; i <= N; i++) {
            result = max(dp[N][i], result);
        }

        bw.write(String.valueOf(result));

        bw.flush();
        br.close();
        bw.close();
    }
}

결론

사실 RGB거리랑 해결방향성이 같다. 해결시간도 2초라서 망설임없이 2중반복문을 사용했다.