🐱 강아지는 많을수록 좋다 (백준 27971)

📌 문제 설명

강아지는 많을수록 좋다

---

💡 핵심 포인트

• 이동 가능한 칸 수는 두 가지(A, B)로 제한됨
• 특정 구간은 사용 불가능하므로 이를 DP에서 제외 처리해야 함
• DP[i] = i번 칸까지 도달하는 최소 점프 횟수로 정의
• 점화식은 가능한 이전 위치에서의 최소 횟수 + 1

---

🔍 풀이 아이디어

1. dp[i]를 i번 칸까지 도달하는 최소 점프 수로 정의
2. 금지 구간은 -1로 마킹하고, 그 외의 구간만 DP로 계산
3. 현재 칸에 도달하려면 i-A 또는 i-B칸에서 왔는지를 검사
4. 둘 다 불가능하면 -1 유지, 둘 중 하나라도 가능하면 그 중 최소값 + 1
5. dp[N]이 최종 정답 (도달 불가능하면 -1)

---

✅ 자바 구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        if(A > B) {
            int swap = A;
            A = B;
            B = swap;
        }

        int[] dp = new int[N + 1];
        dp[0] = 0;

        // 금지 구간 마킹
        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++) {
                dp[j] = -1;
            }
        }

        // DP 계산
        for(int i = 1; i <= N; i++) {
            if(dp[i] == -1) continue;
            if(i < A) {
                dp[i] = -1;
            } else if(i < B) {
                dp[i] = (dp[i - A] == -1) ? -1 : dp[i - A] + 1;
            } else {
                int fromA = (dp[i - A] == -1) ? Integer.MAX_VALUE : dp[i - A] + 1;
                int fromB = (dp[i - B] == -1) ? Integer.MAX_VALUE : dp[i - B] + 1;
                int min = Math.min(fromA, fromB);
                dp[i] = (min == Integer.MAX_VALUE) ? -1 : min;
            }
        }

        System.out.println(dp[N]);
    }
}

---

🧠 배운 점

• 조건문이 복잡할수록, DP 초기값과 금지 구간 마킹을 먼저 깔끔하게 정리해야 전체 흐름이 잘 잡힘
• 점화식보다 상태 정의가 더 중요함. dp[i] = i칸까지 최소 점프 횟수로 정확히 정의했을 때 점화식도 자연스럽게 따라감
• 금지된 위치는 접근 자체가 불가능하므로 -1로 명시적으로 마킹하는 전략이 깔끔하다