[Silver I] 강아지는 많을수록 좋다 - 27971

문제 링크

성능 요약

메모리: 113576 KB, 시간: 124 ms

분류

다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색

제출 일자

2026년 04월 25일 22:04:59

문제 설명

마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 $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$을 출력한다.

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/27971
 
import sys
input = sys.stdin.readline
from collections import deque 
 
 
n, m, a, b = map(int, input().split())
#목표 강쥐수, 닫힌구간 개수, a, b개수
 
 
dog = 0
 
blocked = [0] * (n + 1)
 
for _ in range(m):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        blocked[i] = 1
 
visited = [-1 for i in range(n+1)]
 
 
def bfs():
    q = deque([0])
    visited[0] = 0
    
    while q:
        now = q.popleft()
        if now == n:
            return visited[now]
        
        for way in (now + a, now + b):
            #ㅁㅏ리를 초과하지 않고,  제한 구간에 들어있지 않고, 미방문 구간이라면
            if way <= n and blocked[way] == 0 and visited[way] == -1:
                visited[way] = visited[now] + 1
                q.append(way)   
    return -1
    
    
print(bfs())