[백준 13913] 동전 1

https://www.acmicpc.net/problem/13913 문제이해 n 가지 종류의 동전을 활용해 주어지는 k를 완성하면 된다. 동전의 개수는 무제한이고 사용한 동전의 구성은 같고 순서만 다른 경우는 같은 경우이다.

풀이 BFS -> 메모리 초과 -> DFS -> 재귀 깊이 제한 -> BFS (visited 배열로 이미 방문한 곳 방문하지 않음, 메모리 최적화) -> BFS (방문지마다 방문하기까지의 이동 경로를 저장하지 않고 최종 방문지의 이전 방문지 정보를 visited에 저장해 N이 나올 때까지 찾아감, 시간 최적화) 코드 from collections import deque N, K = map(int, input().split()) d = deque() visited = [-1] * 111111 d.append(N) while d: f = d.popleft() if f == K: break for next in (f+1, f-1, f*2): if 0 <= next <...