[백준][Sliver1]1932 - 정수 삼각형 - JAVA

[문제]

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

1932번: 정수 삼각형

 

[풀이]

* 알고리즘: 다이나믹 프로그래밍

다이나믹 프로그래밍을 이용하여 푸는 문제이다. 

점화식은 쉽게 세울수 있다.

그런데 인덱스를 이용한 삼각형 배열을 만드는 것이 어려웠다.

어려웠던 이유는 1차원 배열로 삼각형을 만드려했기 때문이었다.

2차원 배열로 삼각형을 만드니 쉽게 다이나믹프로그래밍을 이용하여 문제를 풀 수 있었다. 

 

바텀업 방식으로 풀면되는데 현재 위치에서 위로 왼쪽 대각선, 오른쪽 대각선에 있는 수 중 큰 수를 현재값과 더해주면 된다.

그런데 삼각형 매 줄에 가장 왼쪽 숫자는 위에 왼쪽 대각선에 숫자가 없고, 가장 오른쪽 숫자는 위에 가장 오른쪽 숫자가 없다.

그래서 가장 왼쪽 숫자와 가장 오른쪽 숫자는 비교 필요없이 한쪽 대각선에 있는 숫자만 더해주면 된다.

[코드]

package com.algorithm.thisiscodingtest.dp;

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

public class PreviousProblem02 {
    public static int N;
    public static int[][] dp;

    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());
        dp = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int index = 0;
            while (st.hasMoreTokens()) {
                int num = Integer.parseInt(st.nextToken());
                dp[i][index] = num;
                index++;
            }
        }

        solution();

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp[N - 1].length; i++) {
            max = Math.max(max, dp[N - 1][i]);
        }

        bw.write(max + "\n");

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

    public static void solution() {
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    dp[i][j] += dp[i - 1][j];
                } else if (j == i) {
                    dp[i][j] += dp[i - 1][j - 1];
                } else {
                    dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                }
            }
        }
    }
}