[JAVA-자바] 2096번: 내려가기

 

소스코드:

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;

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

        int N = Integer.parseInt(br.readLine());
        int[][] board = new int[N][3];
        int[][] max_dp = new int[N][3];
        int[][] min_dp = new int[N][3];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            board[i][0] = Integer.parseInt(st.nextToken());
            board[i][1] = Integer.parseInt(st.nextToken());
            board[i][2] = Integer.parseInt(st.nextToken());
        }
        br.close();

        // solve
        int max_score = Integer.MIN_VALUE;
        int min_score = Integer.MAX_VALUE;

        if (N == 1) {
            max_score = Math.max(board[0][0], Math.max(board[0][1], board[0][2]));
            min_score = Math.min(board[0][0], Math.min(board[0][1], board[0][2]));
        } else {
            max_dp[0][0] = min_dp[0][0] = board[0][0];
            max_dp[0][1] = min_dp[0][1] = board[0][1];
            max_dp[0][2] = min_dp[0][2] = board[0][2];

            for (int i = 1; i < N; i++) {
                for (int j = 0; j < 3; j++) {
                    if (j == 0) { // left
                        max_dp[i][j] = Math.max(max_dp[i - 1][j], max_dp[i - 1][j + 1]) + board[i][j];
                        min_dp[i][j] = Math.min(min_dp[i - 1][j], min_dp[i - 1][j + 1]) + board[i][j];
                    } else if (j == 2) { // right
                        max_dp[i][j] = Math.max(max_dp[i - 1][j - 1], max_dp[i - 1][j]) + board[i][j];
                        min_dp[i][j] = Math.min(min_dp[i - 1][j - 1], min_dp[i - 1][j]) + board[i][j];
                    } else {
                        max_dp[i][j] = Math.max(max_dp[i - 1][j], Math.max(max_dp[i - 1][j - 1], max_dp[i - 1][j + 1]))
                                + board[i][j];
                        min_dp[i][j] = Math.min(min_dp[i - 1][j], Math.min(min_dp[i - 1][j - 1], min_dp[i - 1][j + 1]))
                                + board[i][j];
                    }
                    if (i == N - 1) {
                        max_score = Math.max(max_score, max_dp[i][j]);
                        min_score = Math.min(min_score, min_dp[i][j]);
                    }
                }
            }
        }

        bw.write(max_score + " " + min_score + "\n");
        bw.close();
    }
}

 

글의 내용 중 잘못된 점이나 수정이 필요한 부분, 혹은 궁금한 사항이 있다면 언제든 댓글로 남겨주시면 감사하겠습니다.

여러분의 피드백은 더 나은 글을 작성하는 데 큰 도움이 됩니다. 감사합니다.