[99클럽 코테 스터디 18일차 TIL + DP] 백준 27971 강아지는 많을수록 좋다 파이썬

오늘의 학습 키워드

DP(Dynamic Programming)

공부한 내용 본인의 언어로 정리하기

문제

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

코드

from collections import deque

n, m, a, b = map(int, input().split())
arr = set()
for _ in range(m):
    i, j = map(int, input().split())
    for k in range(i, j+1):
        if k not in arr:
            arr.add(k)

visited = [0] * (n+1)

def bfs(start):
    q = deque()
    q.append(start)
    visited[start] = 1
    count = 0
    while q:
        now = q.popleft()
        for i in [a, b]:
            new = now + i
            if new <= n and visited[new] == 0 and new not in arr:
                visited[new] = visited[now] + 1
                if new == n:
                    return visited[new]-1
                else:
                    q.append(new)


answer = bfs(0)
print(-1 if not answer else answer)

 

주어진 범위 내에 들어가지 않으면서 강아지를 만들 수 있는 최소 값을 찾는 것임으로, bfs를 통해 해당 값을 찾아주었다. 구현하면서 가장 중요했던 것은 특정 범위 안에 들지 않는 것이었는데, 해당 범위를 set을 통해 형성하고 new 값을 생성할 때마다 set 내의 값과 비교함으로써 범위를 피해갈 수 있었다. 

오늘의 회고

DP문제처럼 보이는 것도 dfs/bfs로 풀 수 있다는 것을 깨달았다. 나에게 DP는 막연하게 어려운 문제인데 익숙한 bfs로 푸니 어렵지 않고 수월하게 해결할 수 있었던 것 같다. 처음에는 범위를 list로 구현했었는데 해당 방법이 시간복잡도 측면에서 좋지 않아 set으로 다시 바꿔주었다. set이 list보다 시간복잡도 측면에서 좋다는 것을 배울 수 있었다.