algorithms 백준 (BOJ)

[BOJ]백준 1932번: 정수 삼각형 (baekjoon 1932)

2020.01.26 ·

(BOJ)백준 1932 - 1932번: 정수 삼각형

1932번: 정수 삼각형

[BOJ] 백준 (1932)

백준 1932 - 1932번: 정수 삼각형

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

코드

import java.io.*;

public class B1932 {
    static int n;
    static int[][] t = new int[501][501];
    static String[] ins;
    static int[][] dp = new int[502][502];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            ins = br.readLine().split(" ");
            for (int j = 0; j < i; j++) {
                t[i][j] = Integer.parseInt(ins[j]);
            }
        }
        dp[1][0] = t[1][0];
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                int prev = j - 1, next = j;
                if (prev > -1) dp[i][j] = dp[i - 1][prev] + t[i][j];
                if (next < i - 1) dp[i][j] = Math.max(dp[i][j], dp[i - 1][next] + t[i][j]);
            }
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, dp[n][i]);
        }
        bw.write(max + "\n");
        bw.flush();bw.close();
    }
}

설명