[BOJ] 27971. 강아지는 많을수록 좋다 (🥈, DP)

🔗

풀이

닫힌 구간들에 대해서는 건너뛰면서 A, B 만큼 이동했을 때 최소 이동 횟수인 값을 저장해나가는 dp로 풀이했다.

닫힌 구간들이 100개 정도 주어지고 해당할 수 있는 범위는 각 구간별로 최대 10만이므로 10만 x 100 을 일일이 표시하면 시간초과가 날 것 같았다. 그래서 모든 구간에 대해 구간의 양끝에만 L은 -1 R은 +1 표시를 해서 누적합으로 전체 값을 계산했다. 이렇게 하면 구간에 해당하는 부분은 값의 크기에 상관없이 무조건 음수를 갖게 된다. 음수의 값을 갖는 칸들은 피하면 된다.

음수의 값을 갖지 않는 모든 값에 대해서 A와 B 만큼 이동시켜보고, 이동한 칸에 대해서 최소 이동횟수를 갖는 값을 저장한다. 구간에 해당하는 값은 arr 에 저장되어 있으므로 arr[i] 가 음수라면 해당 칸에 대한 연산은 건너뛴다. 이동 횟수에 대한 값은 dp에 저장되므로 dp는 초반에는 int의 최대값을 저장해놓고 계속해서 최소 값으로 업데이트 해나가면 된다.

마지막으로 N에 위치한 값이 Integar.MAX_VALUE 와 같다면 해당 칸에 도달할 수 없었던 것이므로 -1을 출력하고 아니라면 해당 칸에 적힌 최소 이동 횟수를 출력한다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();

        int[] arr = new int[N+1];
        int l; int r;
        for (int i = 0; i < M; i++) {
            l = sc.nextInt();
            r = sc.nextInt();
            arr[l] -= 1;
            arr[r + 1] += 1;
        }

        for (int i = 1; i < N + 1; i++) {
            arr[i] += arr[i - 1];
        }

        int[] dp = new int[N + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < N + 1; i++) {
            if (arr[i] < 0 || dp[i] == Integer.MAX_VALUE) {
                continue;
            }

            if (i + A <= N) {
                dp[i + A] = Math.min(dp[i + A], dp[i] + 1);
            }

            if (i + B <= N) {
                dp[i + B] = Math.min(dp[i + B], dp[i] + 1);
            }
        }

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