백준 - 1932 정수 삼각형(Java)

 

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

1932번: 정수 삼각형

 

DP 문제입니다.

문제에 의하면 위에서 부터 좌측 하단 또는 우측 하단 둘 중 하나를 선택하여 최하단으로 내려왔을 때, 합이 최대가 되게 만들어야 합니다.

이를 반대로 생각하면 현재 위치에서의 최대는 좌측 상단 또는 우측 상단의 최대를 선택해 현재를 더하면 됩니다.

현재를 (i, j)라고 했을 때, 좌측 상단 및 우측 상단의 좌표 값은 다음과 같습니다.

좌측 상단 : (i-1, j-1)

우측 상단 : (i-1, j)

즉, 점화식은 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + map[i][j] 과 같습니다.

이런 방식을 Bottom-Up 방식이라 합니다.

 

[구현 코드]

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

public class Main {
    private static int n, answer;
    private static final int LIMIT = -1;
    private static int[][] map, 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));
        StringTokenizer stz;

        n = Integer.parseInt(br.readLine());
        map = new int[n + 1][n + 1];
        dp = new int[n + 1][n + 1];

        for (int i = 1; i < n + 1; i++) {
            Arrays.fill(map[i], LIMIT);
        }


        for (int i = 1; i < n + 1; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j < i+1; j++) {
                map[i][j] = Integer.parseInt(stz.nextToken());
            }
        }

        // bottom-up 방식
        answer = bottomUp();

        // 정답 출력
        bw.write(String.valueOf(answer));

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

    }

    private static int bottomUp(){
        // 현재를 기준으로 좌측 상단과 우측 상단을 비교하여 큰 값을 가져옴
        dp[1][1] = map[1][1];
        for(int i=2; i<n+1; i++){
            for(int j=1; j<i+1; j++){
                int leftTop = dp[i-1][j-1];
                int rightTop = dp[i-1][j];

                dp[i][j] = Math.max(leftTop, rightTop) + map[i][j];
            }
        }

        int ans = 0;
        for(int i=1; i<n+1; i++){
            ans = Math.max(ans, dp[n][i]);
        }
        return ans;
    }
}