[백준] 28017: 게임을 클리어하자 - JAVA

25 May 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

dp문제이다.

이전 회차의 무기 선택이 현재 회차의 선택에 영향을 미친다.

이전 회차까지의 최솟값을 구해놓고 최솟값에 현재 회차의 선택을 더해준다.

현재 선택한 무기가 이전 회차에서 선택한 무기와 같다면 그 다음 최솟값을 구하여 더해준다.

---

메모리: 36792KB

시간: 652ms

언어: Java 11

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        for (int i = 1; i < N; i++) {
            int prev = Integer.MAX_VALUE;
            for (int j = 0; j < M; j++) {
                prev = Math.min(prev, dp[i - 1][j]);
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
                if (dp[i - 1][j] != prev) {
                    dp[i][j] += prev;
                } else {
                    int min = Integer.MAX_VALUE;
                    for (int k = 0; k < M; k++) {
                        if (k == j) {
                            continue;
                        }
                        min = Math.min(min, dp[i - 1][k]);
                    }
                    dp[i][j] += min;
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < M; i++) {
            ans = Math.min(ans, dp[N - 1][i]);
        }

        System.out.println(ans);

    }

}