[99클럽 코테 스터디 18일차 TIL] 강아지는 많을수록 좋다

 

18일차 문제

링크 : https://www.acmicpc.net/problem/27971

 

 

 

문제 풀이

문제를 보고 BFS로 풀어야 하나, DP로 풀어야 할까 고민하다가 DP가 더 간단한 것 같아 DP로 풀이하였다.

 

점화식

dp[i] : 강아지 i마리를 만들기 위한 최소 마법 사용 횟수

dp[i] = min(dp[i], dp[i - A] + 1) (i ≥ A)
dp[i] = min(dp[i], dp[i - B] + 1) (i ≥ B)

-> dp[i] 중에서 닫힌 구간에 포함되지 않는 것도 고려

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 강아지 수
        int M = Integer.parseInt(st.nextToken()); // 닫힌구간 개수
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        boolean closed[] = new boolean[N+1];

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            for(int j=s; j<=e && j<=N; j++) {
                closed[j] = true;
            }
        }

        int[] dp = new int[N+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for(int i=1; i<dp.length; i++) {
            // 닫힌구간 패스
            if(closed[i]) {
                continue;
            }

            if(i>=A && !closed[i-A] && dp[i-A] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i-A] + 1);
            }

            if(i>=B && !closed[i-B] && dp[i-B] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i-B] + 1);
            }
        }

        if(dp[N] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(dp[N]);
        }
    }
}