99클럽 코테 스터디 18일차 TIL + BFS

https://www.acmicpc.net/problem/27971

import sys
from collections import deque

input = sys.stdin.readline

n,m,a,b = map(int, input().split())
dp = [0] * (n+1)
visited = [False] * (n+1)

for _ in range(m):
    l,r = map(int, input().split())
    for i in range(l, r+1):
        visited[i] = True # 닫힌구간 방문처리

dp[n] = 0
q = deque()
q.append(n)
while q:
    value = q.popleft()
    if value == 0:
        break
    for i in (value-a, value-b):
        if i >= 0:
            if visited[i]:
                continue
            else:
                q.append(i)
                dp[i] = dp[value] + 1
                visited[i] = True

if dp[0]:
    print(dp[0])
else:
    print(-1)

• dp로 많이 풀지만 점화식을 생각하지 못해 bfs로 풀이했다.
• n마리를 생성했다고 하고 a, b마리씩 빼준다.
• visited 리스트를 사용하여 닫힌 구간은 방문했다 라고 가정한다.
• 그러므로 visited 리스트 값이 False라면 큐에 넣고 방문처리를 한다.