징검다리 건너기

문제

21317번: 징검다리 건너기

문제 설명

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

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

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

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

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

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

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

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

제한 사항

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

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

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

입출력 예

입력	출력
5
1 2
2 3
4 5
6 7
4	5

제출 코드

import java.io.IOException;
import java.util.Scanner;

public class one21317 {
    private int n;
    private int[][] jump;
    private int k;
    private int result = Integer.MAX_VALUE;

    public void solution() throws IOException {
        Scanner sc = new Scanner(System.in);
        // 돌의 개수
        n = sc.nextInt();
        jump = new int[n][2];
        // 작은 점프와 큰 점프
        for (int i = 1; i < n; i++) {
            jump[i][0] = sc.nextInt();
            jump[i][1] = sc.nextInt();
        }
        // 매우 큰 점프
        k = sc.nextInt();

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

    private void dfs(int cur, boolean used, int value) {
        if (cur == n) {
            result = Math.min(result, value);
            return;
        }

        if (value > result) {
            return;
        }

        if (cur + 1 <= n) {
            dfs(cur + 1, used, value + jump[cur][0]);
        }

        if (cur + 2 <= n) {
            dfs(cur + 2, used, value + jump[cur][1]);
        }

        if (!used && cur + 3 <= n) {
            dfs(cur + 3, true, value + k);
        }
    }

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