핵심 아이디어

<aside> 💡

• $dp_i =$ 강아지가 $i$마리가 있는 상태로 만들기 위한 최소 마법 사용 횟수.
• 이때 $i$가 $[L, R]$사이에 포함되는 숫자라면 $dp_i = -1$
• $dp_{i-A} \ne -1, dp_{i-B} \ne -1 \text{인 경우:}\ dp_i = min(dp_{i-A}, dp_{i-B})$
• $dp_{i-A} = -1, dp_{i-B} \ne -1 \text{인 경우:}\ dp_i = dp_{i-B}$
• $dp_{i-A} \ne -1, dp_{i-B} = -1 \text{인 경우:}\ dp_i = dp_{i-A}$
• $dp_{i-A} = -1, dp_{i-B} = -1 \text{인 경우:}\ dp_i = -1$ </aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;
#define INF 2139062143

int N, M, A, B;
pair<int, int> lr[101]; 

int dp[100'001];

int go(int cur)
{
    int &ret = dp[cur];
    if(ret != INF) return ret;

    int dp1 = INF;
    int dp2 = INF;
    bool flag1 = true;
    bool flag2 = true;

    for(int i = 0; i<M; i++){
        auto[l, r] = lr[i];
        if(l<=cur-A && cur-A<=r) flag1 = false;
        if(l<=cur-B && cur-B<=r) flag2 = false;
    }

    if(flag1 && cur-A>=0) dp1 = go(cur-A);
    if(flag2 && cur-B>=0) dp2 = go(cur-B);

    return ret = min(dp1, dp2)+1;
}

signed main()
{
    FASTIO;
    cin >> N >> M >> A >> B;
    for(int i = 0; i<M; i++){
        int l, r; cin >> l >> r;
        lr[i] = {l, r};
    }

    memset(dp, 0x7f, sizeof(int)*(N+1));
    dp[0] = 0;
    int ans = go(N);

    if(ans >= INF) cout << "-1\\n";
    else cout << ans <<"\\n";

    return 0;
}