[백준 27971번] 파이썬 - 강아지는 많은 수록 좋다

백준 27971 - 강아지는 많은수록 좋다

시간 제한 2초, 메모리 제한 1024MB

# 조건

• 마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 N마리를 집에서 키우기로 결심했다!
• 호무라는 한 번의 행동에서 다음 2가지 마법 중 하나를 선택하여 사용한다.
• 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다.
  • A마법 - 강아지 A마리를 호무라의 집에 생성한다.
  • B마법 - 강아지 B마리를 호무라의 집에 생성한다.
• 그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다.
• 만약 호무라의 방에 생성된 강아지의 수가 M개의 닫힌 구간들 [L1, R1], [L2, R2], ... [Lm, Rm] 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다.
• 이를 명심하면서, 호무라는 위의 2가지 마법을 적절히 사용하여, 최소의 행동 횟수로 호무라의 집에 정확인 N마리의 강아지가 있도록 만들고 싶다.
• 계산을 어려워하는 호무라를 위해 최소의 행동 횟수를 계산해주자!

입력

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

출력

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

# 접근 방법

• DP 또는 BFS를 이용하여 풀어준다.
• dp 이용
  • N+1 크기의 최대값을 가진 리스트를 만들어주고 닫힌 구간은 -1로 표시해준다.
  • 1부터 N까지 반복문을 돌리며 범위 내에 있고, DP 리스트가 -1 이 아니라면
  • i-A와 i-B 값이 유효한 값이면 dp값에서 최소를 뽑아주고,
  • 둘 중 하나만 유효하다면 현재 인덱스 + 1과 이전 값 + 1 을 비교하여 최소로 기록해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

INF = float('inf')  
N, M, A, B = map(int, input().split())  
dp = [INF] * (N+1)  
dp[0] = 0  
for _ in range(M):  
    a, b = map(int, input().split())  
    for i in range(a, b+1):  
        dp[i] = -1  

for i in range(1, N+1):  
    if dp[i] < 0:  
        continue  

    ma = i - A  
    mb = i - B  
    if 0<=ma and dp[ma] != -1:  
        dp[i] = min(dp[ma]+1, dp[i])  
    if 0<=mb and dp[mb] != -1:  
        dp[i] = min(dp[mb]+1, dp[i])  


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

• bfs 이용
  • N+1 크기의 리스트를 만들어주고 뒤에서 부터 마법을 통해 생성이 아닌 빼주는 걸로 해준다.
  • 또한 visited 배열을 이용하여 M개의 닫힌 구간을 표시해준다.
  • N번 인덱스부터 시작하여 A만큼, B만큼 뺀 것을 + 1 씩 해주면서 진행한다.
  • VISITED 배열에서 True이면 닫힌 구간에 존재하는 것이므로 continue
    • False라면 큐에 넣고 visited True로 변경해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

N, M, A, B = map(int, input().split())  
dp = [0] * (N+1)  
visited = [False] * (N+1)  

for _ in range(M):  
    a, b = map(int, input().split())  
    for i in range(a, b+1):  
        visited[i] = True  

dp[N] = 0  
q = deque()  
q.append(N)  
while q:  
    val = q.popleft()  
    if val == 0:  
        break  
    for i in (val-A, val-B):  
        if i >= 0:  
            if visited[i]:  
                continue  
            else:  
                q.append(i)  
                dp[i] = dp[val] + 1  
                visited[i] = True  
if dp[0]:  
    print(dp[0])  
else:  
    print(-1)