징검다리 건너기 - 21317번

---

풀이 방법

다이나믹 프로그래밍을 사용해서 풀이했다.

중요한 게 매우 큰 점프를 한번만 사용할 수 있다는 것이다.

그래서 매우 큰 점프를 사용할 수 있는 모든 경우의 수에 넣어주었다.

나머지는 DP의 Bottom-Up 방식으로 풀이하면 된다. 

 

 

내 코드

package com.company;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

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

        int N = Integer.parseInt(br.readLine());

        int array[][] = new int[N + 1][2];

        array[0][0] = 5000;
        array[0][1] = 5000;

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            array[i][0] = Integer.parseInt(st.nextToken());
            array[i][1] = Integer.parseInt(st.nextToken());
        }
        array[N][0] = 0;
        array[N][1] = 0;

        int K = Integer.parseInt(br.readLine());

        int min = (int) 1e9;

        for (int j = 0; j <= N; j++) {
            int d[] = new int[N + 1];

            for (int i = 2; i <= N; i++) {
                d[i] = Math.min(d[i - 1] + array[i - 1][0], d[i - 2] + array[i - 2][1]);
                if (i == j && j > 3) {
                    d[i] = Math.min(d[i - 3] + K, d[i]);
                }
            }
            min = Math.min(d[N], min);
        }

        System.out.println(min);
    }
}