[백준] Silver 1. 징검다리 건너기

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

 

사용 알고리즘

• DFS

풀이

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[] jump1, jump2;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        jump1 = new int[n];
        jump2 = new int[n];

        for(int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            jump1[i] = a;
            jump2[i] = b;
        }
        k = Integer.parseInt(br.readLine());

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

    public static void dfs (int start, int energy, boolean isUsed) {
        if (start == n) {
            min = Math.min(min ,energy);
            return;
        }

        if (start + 1 <= n) dfs(start + 1, energy + jump1[start], isUsed);
        if (start + 2 <= n) dfs(start + 2, energy + jump2[start], isUsed);
        if (!isUsed && start + 3 <= n) dfs(start + 3, energy + k, true);
    }
}

 

 

회고

 

문제 분류는 다이나믹 프로그래밍이지만, N이 20까지로 숫자가 작기도 했고 풀이가 떠오르지 않아서 dfs로 문제를 해결해줬다. 범위 조건을 체크하는 것 이외에도, 매우 큰 점프는 딱 한번 사용이 가능하기 때문에 boolean 파라미터를 추가해줘서 조건 체크를 했다. 

 

처음에 for문을 사용해서 문제를 풀려고 했는데 점프의 거리가 각각 다르기 때문에 이렇게 처리하면 안된다..! 점프의 길이가 1,2,3일때 각각 케이스를 나눠서 백트래킹을 돌려줘야하는 문제였다.