백준 21317[자바] java 징검다리 건너기

문제 링크: https://www.acmicpc.net/problem/21317

21317번: 징검다리 건너기

▶문제

심마니 영재는 산삼을 찾아다닌다.

산삼을 찾던 영재는 N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.

마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.

점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.

각 점프를 할 때는 에너지를 소비하는데, 이때 작은 점프와 큰 점프 시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.

매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.

에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.

영재는 첫 번째 돌에서부터 출발한다.

---

▶입력

첫 번째 줄에는 돌의 개수 N이 주어진다.

N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다.

마지막 줄에는 K가 주어진다.

---

▶출력

산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.

---

▶해설

간단한 DFS 문제입니다. 한 칸 or 두 칸 or 한 번의 기회만 주어지는 3칸을 넘어갔을 때 값들을 탐색하면 됩니다.

(단 세 칸을 넘어갔을 때 체크를 하고 세 칸을 두 번 넘어가는 경우가 없게 해야합니다.)

 

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


public class Main {
    static int n;
    static int answer = Integer.MAX_VALUE;
    static int [][] arr;
    static int k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n+1][2];
        int small;
        int big;
        for(int i=1; i<=n-1; i++) {
            String[] s = br.readLine().split(" ");
            small = Integer.parseInt(s[0]);
            big = Integer.parseInt(s[1]);
            arr[i][0]=small;
            arr[i][1]=big;
        }
        k = Integer.parseInt(br.readLine());

        dfs(0,1,false);
        System.out.println(answer);
    }

    private static void dfs(int sum, int to, boolean flag){
        if(to==n){
            answer = Math.min(answer,sum);
            return;
        }

        if(to>n){
            return;
        }

        dfs(sum+arr[to][0],to+1,flag); // 한 칸 넘어갈 때
        dfs(sum+arr[to][1],to+2,flag); // 두 칸 넘어갈 때

        if(!flag){ // 한 번 주어지는 세 칸 넘어갈 때 체크해줍니다.
            dfs(sum+k, to+3, true);
        }
    }
}

(DP로 푸는 방법도 있다고 들었는데 나중에 다시 해보겠습니다..)