[자바] 백준 28017 - 게임을 클리어하자 (java)

목차

문제 : boj28017

 

 

필요 알고리즘

• 다이나믹 프로그래밍 (DP, 동적 계획법)
  
  • DP로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  개인적으로 국어문제였다.. '바로 이전 회차의 무기는 사용하지 않기로' 라고 써있는걸 대충 읽고 넘어가서, '이전에 사용한 무기는 사용 않기로'로 해석했다 ㅋㅋ. 덕분에 "와.. 비트 dp도 안되는데 이걸 어떻게 한거지? 최소 3~4 차원 dp는 필요할 것 같은데;; 이게 골드5라고? 다들 얼마나 괴물들인거야?" 생각하고 있었다.. ㅠ 결론적으로 직전에 사용한것만 안쓰면 된다는걸 깨달은 후로 10분도 안걸려서 푼 것 같다.

 

  dp[a][b]를 a회차에서 b 무기를 쓸 때의 최소 시간이라 하자. 그리고 arr[a][b]는 a회차에서 b무기를 쓸 때 걸리는 시간이다(입력값 자체).

그럼 점화식은 'dp[a][b] = arr[a][b] + min(dp[a-1][0], dp[a-1][1],  ... + dp[a-1][M])' 이다(단, min() 부분에서 직전에 사용한 무기는 사용하면 안되므로 dp[a-1][b]는 제외한다.).

최종적으로 min(dp[N][0], dp[N][1], ..., dp[N][M])이 답이다. 

 

코드 : github

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

import static java.lang.Math.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] dp = new int[m];
        while (n-->0) {
            st = new StringTokenizer(br.readLine());
            int[] curDp = new int[m];
            for (int i = 0; i < m; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < m; j++) {
                    if (i == j) continue;

                    min = min(min, dp[j]);
                }

                curDp[i] = Integer.parseInt(st.nextToken()) + min;
            }
            dp = curDp;
        }

        System.out.println(Arrays.stream(dp).min().getAsInt());
    }
}