[BOJ_21317] 징검다리 건너기

설명

---

 

푸는데 걸린 시간은 매우 짧았지만 고민을 하면서 이 코드가 맞을지 확신을 가지지 못한채로 풀이를 진행했던 문제입니다.

DP가 아직 익숙치 않으니 점화식을 짜는 것이 어색합니다. 빅 점프를 한 번만 할 수 있으므로 모든 경우에서 빅점프를 할 수 있는 경우를 열어 두고 빅 점프 이후에 다시 DP를 초기화하면서 점프에 대한 초기화를 진행하였습니다.

 

N이 20이라 가능 한 경우이지 이렇게 매번 초기화 하는 방법 보다 index 값을 넘겨줘서 해당 index 이후로 부터만 보면 된다는 최적화식을 세울 수 도 있을 것이고 다른 좋은 방법이 있을겁니다.

 

 

코드

---

 

package BOJ.Dynamic_Programming;

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

public class BOJ_21317 {
    static int N,K,ans;
    static int[] small,big;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(in.readLine());
        StringTokenizer tk;

        small = new int[N];

        big = new int[N];
        int initDP[] = new int[N];

        for (int i = 0; i < N - 1; i++){
            tk = new StringTokenizer(in.readLine(), " ");
            small[i] = Integer.parseInt(tk.nextToken());
            big[i] = Integer.parseInt(tk.nextToken());
        }
        K = Integer.parseInt(in.readLine());
        if(N == 1){
            System.out.println(small[0]);
            return;
        }
        initDP[0] = 0;
        initDP[1] = small[0];

        for (int i = 2; i < N; i++)
        {
            initDP[i] = Math.min(initDP[i - 1] + small[i - 1], initDP[i - 2] + big[i - 2]);
        }



        int[] tmpDP = new int[N];
        copyOfArray(initDP,tmpDP);

        ans = Integer.MAX_VALUE;
        for (int i = 3; i < N; i++)
        {
            if (initDP[i - 3] + K < initDP[i]){
                tmpDP[i] = initDP[i - 3] + K;
                ans = Math.min(makeDP(tmpDP),ans);
                copyOfArray(initDP, tmpDP);
            }
        }
        System.out.println(Math.min(ans, initDP[N - 1]));
    }

    private static void copyOfArray(int[] src, int[] des){
        for (int i = 0; i < src.length; i++){
            des[i] = src[i];
        }
    }
    private static int makeDP(int[] tmpDp){
        for (int i = 2; i < N; i++)
        {
            tmpDp[i] = Math.min(Math.min(tmpDp[i - 1] + small[i - 1], tmpDp[i - 2] + big[i - 2]), tmpDp[i]);
        }
        return tmpDp[N - 1];
    }
}

21317번: 징검다리 건너기