You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
python3
import sys
from collections import deque
n,k = map(int,sys.stdin.readline().split())
q = deque([])
arr = []
for _ in range(n):
x = int(sys.stdin.readline())
q.append([x,1])
arr.append(x)
visit = [False for _ in range(10001)]
while q:
check = 0
x,y = q.popleft()
for j in arr:
if x+j < k:
if visit[x+j] == False:
visit[x+j] = True
q.append([x+j,y+1])
elif x+j == k:
print(y+1)
exit(0)
print(-1)
DP문제지만 BFS를 응용해서 풀어봤다.
사용한 동전의 총개수가 중요하기 때문에 동전이 1개일때 부터 시작해서 2개로 만들 수 있는 경우 3개로 만들 수 있는 경우 전부 찾아보는것이다.
만약에 처음으로 k와 같은 값이 나온다면 해당 값이 가장 작은 개수의 동전으로 만든 값이 된다.
가중치가 1인 그래프 문제로 볼 수도 있는 것이다.
해당 조건에서 BFS는 최단거리를 보장하기 때문에 위와 같은 풀이가 가능하다.
그리고 한번 만든 금액의 합 값은 다시 만들 필요가 없기에 방문 할때마다 visit 배열에 방문처리를 해준다.
이러면 메모리 초과를 면할 수 있다.
만약에 계속 값이 증가해서 k보다 커지게 된다면 몇번 더 돌다가 결국 q는 빈 리스트가 되고 프로그램이 끝난다.
그래도 뭐 아이디어 자체는 DP가 추구하는 이전 값을 낭비하지 않고 쓰는게 맞긴 하니깐..
우리는 이걸 DP라 부를 수 있을까요?
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
https://www.acmicpc.net/problem/2294
DP문제지만 BFS를 응용해서 풀어봤다.
사용한 동전의 총개수가 중요하기 때문에 동전이 1개일때 부터 시작해서 2개로 만들 수 있는 경우 3개로 만들 수 있는 경우 전부 찾아보는것이다.
만약에 처음으로 k와 같은 값이 나온다면 해당 값이 가장 작은 개수의 동전으로 만든 값이 된다.
가중치가 1인 그래프 문제로 볼 수도 있는 것이다.
해당 조건에서 BFS는 최단거리를 보장하기 때문에 위와 같은 풀이가 가능하다.
그리고 한번 만든 금액의 합 값은 다시 만들 필요가 없기에 방문 할때마다 visit 배열에 방문처리를 해준다.
이러면 메모리 초과를 면할 수 있다.
만약에 계속 값이 증가해서 k보다 커지게 된다면 몇번 더 돌다가 결국 q는 빈 리스트가 되고 프로그램이 끝난다.
그래도 뭐 아이디어 자체는 DP가 추구하는 이전 값을 낭비하지 않고 쓰는게 맞긴 하니깐..
우리는 이걸 DP라 부를 수 있을까요?
Beta Was this translation helpful? Give feedback.
All reactions