[BOJ] 27971번 강아지는 많을수록 좋다 - 파이썬

📒 문제

마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 $N$마리를 집에서 키우기로 결심했다!

호무라는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다.

 $A$-생성 마법: 강아지 $A$마리를 호무라의 집에 생성한다.
$B$-생성 마법: 강아지 $B$마리를 호무라의 집에 생성한다.
그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 $M$개의 닫힌구간들 ${[L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]}$ 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다!

이를 명심하면서, 호무라는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 호무라의 집에 정확히 $N$마리의 강아지가 있도록 만들고 싶다. 계산을 어려워하는 호무라를 위해 최소의 행동 횟수를 계산해주자!

입력

첫 번째 줄에 키우기를 원하는 강아지의 수 $N (2\leq N\leq 100\,000)$, 제약 사항에 해당하는 닫힌구간의 개수 $M (1\leq M\leq 100)$, 그리고 $A$와 $B (1\leq A,B\leq N)$가 띄어쓰기로 구분되어 주어진다. 그 다음 $M$줄에 걸쳐서, 각 줄에 제약 사항에 해당하는 닫힌구간의 양 끝점이 주어진다. $1\leq i\leq M$에 대하여 $L_i$와 $R_i$는 $1$ 이상 $N-1$ 이하의 정수이며, $L_i\leq R_i$이다.

출력

첫 번째 줄에 정확히 $N$마리의 강아지를 호무라의 집에 들일 수 있는 최소의 행동 횟수를 출력한다. 만약 불가능하다면 $-1$을 출력한다.

✏️ 풀이

n, m, a, b = list(map(int, input().split()))

dp = [0] * (n+1)

for _ in range(m):
    i, j = list(map(int, input().split()))
    dp[i:j+1] = [-1]*(j-i+1)

if dp[a] != -1:
    dp[a] = 1
if dp[b] != -1:
    dp[b] = 1
a, b = min(a, b), max(a, b)
dp[:a] = [-1]*a
if dp[n] == -1:
    print(dp[n])
else:
    dp[0] = 0
    for i in range(a, n+1):
        if dp[i] != 0:
            continue
        if i < b:
            if dp[i-a] == -1:
                dp[i] = -1
                continue
            dp[i] = dp[i-a] + 1
            continue
        if dp[i-a] == dp[i-b] == -1:
            dp[i] = -1
            continue
        if dp[i-a] == -1:
            dp[i] = dp[i-b] + 1
        elif dp[i-b] == -1:
            dp[i] = dp[i-a] + 1
        else:
            dp[i] = min(dp[i-a], dp[i-b]) + 1

    print(dp[n])