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

문제 바로가기 : https://www.acmicpc.net/problem/28017

메모리 : 36152KB

시간 : 992ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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 + 1][M];
        //max값으로 초기화
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int tmp = Integer.parseInt(st.nextToken());
                //선택할 수 있는 무기들 중 최솟값을 저장한다.
                for (int k = 0; k < M; k++) {
                    if (j != k) {
                        dp[i][j] = Math.min(dp[i - 1][k] + tmp, dp[i][j]);
                    }
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < M; i++) {
            ans = Math.min(dp[N][i], ans);
        }
        System.out.println(ans);
    }
}

풀이

다음 무기를 선택하면서 전 무기의 영향을 받는다. 전 무기와 같은 무기를 선택할 수 없기 때문이다. 따라서 전의 선택이 현재에 영향을 미친다. dp로 선택을 저장하며 현재 선택할 수 있는 무기들 중 최솟값을 구해야 한다.