백준 (BOJ) 21317 징검다리 건너기 java dp

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

21317번: 징검다리 건너기

 

 

체감상 표기된 난이도 보다 훨씬 어려웠던 문제  =,.=

 

가지치기가 중요한 백트래킹 + dp이다.

 

1. 작은 점프로 분기

2. 큰 점프로 분기

3. 매우 큰 점프로 분기

 

dfs를 통해 세 가지 방식 모두로 분기하는 브루트 포스로 처음 방향을 잡고,

 

dfs에서,

1. dp가 비어있다면(==0), 그대로 기대치 에너지 값으로 초기화

2-1. 비어 있지 않은 상황에서 기존에 저장된 값이 기대치 에너지 보다 작다면 후보군 제외 (return 종료)

2-2. 비어 있지 않은 상황에서 기대치 에너지가 더 작다면 후보가 될 수 있으므로 저장 현 위치에 저장

 

탐색을 마친 후에도 적정한 답(최소의 에너지)을 찾아야 한다.

 

매우 큰 점프를 썼냐/안 썼냐를 기준으로 찾게 된다.

 

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

public class Main {
    static int N, K;
    static int[][] jumpEnergy, dp;

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

        jumpEnergy = new int[N][2]; // 0: 작은 점프, 1: 큰 점프
        dp = new int[N][2];
        for(int i=0; i<N-1; ++i){
            st = new StringTokenizer(br.readLine());
            jumpEnergy[i][0] = Integer.parseInt(st.nextToken());
            jumpEnergy[i][1] = Integer.parseInt(st.nextToken());
        }

        K = Integer.parseInt(br.readLine());
        dfs(0,0,0);

        int ans;
        if(dp[N-1][0] == 0){ // 매큰점 안 썼
            ans = dp[N-1][1];
        }
        else if(dp[N-1][1] == 0){ // 매큰점 썼
            ans = dp[N-1][0];
        }
        else{
            ans = Math.min(dp[N-1][0], dp[N-1][1]);
        }

        System.out.print(ans);
    }

    static void dfs(int idx, int energy, int biggestJump){
        // 탈출 조건
        if(N <= idx) return;

        if(dp[idx][biggestJump] == 0){
            dp[idx][biggestJump] = energy; // initialization
        }
        else{
            // 기대 에너지가 기존 최소치 보다 더 크다면 더 볼 것도 없다.
            if(dp[idx][biggestJump] < energy) return; // 끝에 도달하면 초기화되거나 종료 되거나

            dp[idx][biggestJump] = energy;
        }

        // 3가지 전부 다 뛰는 방식으로..!
        // 작은 점프
        dfs(idx+1, energy+jumpEnergy[idx][0], biggestJump);
        // 큰 점프
        dfs(idx+2, energy+jumpEnergy[idx][1], biggestJump);
        // 매우 큰 점프
        if(biggestJump == 0) dfs(idx+3, energy+K, 1);
    }
}