99클럽 코테 스터디 18일차 TIL + 강아지는 많을 수록 좋다

문제

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

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

•  A-생성 마법: 강아지 A마리를 호무라의 집에 생성한다.
•  B-생성 마법: 강아지 B마리를 호무라의 집에 생성한다.

그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 M개의 닫힌구간들 [L1,R1],[L2,R2],⋯,[LM,RM] 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다!

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

입력

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

출력

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

 

 

---

풀이

import sys
input = sys.stdin.readline

N, M, A, B = map(int, input().split())
dis = []
for _ in range(M):
    L, R = map(int, input().split())
    dis.append((L, R))

INF = int(1e9)
dp = [INF] * (N + 1)
dp[0] = 0

def room(num):
    for L, R in dis:
        if L <= num <= R:
            return True
    return False

for i in range(1, N+1):
    if room(i):
        continue
    if i-A >= 0 and not room(i-A):
        dp[i] = min(dp[i], dp[i-A]+1)
    if i-B >= 0 and not room(i-B):
        dp[i] = min(dp[i], dp[i-B] + 1)

if dp[N] != INF:
    print(dp[N])
else:
    print(-1)

 

안익숙한 디피

항해 끝나면 풀었던 것들 다시 복습해야할 것 같다

i는 현재 도착하려는 방 번호..!

i-A와 i-B는 직전에 있었던 방이므로 비교~,,~

 

+BFS로도 풀 수 있는 문제이다

 

문제 출처

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