교대최소제곱법
[백준 파이썬 2294번 동전 2] 메모리 초과 문제 해결 본문
https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어
www.acmicpc.net
BFS로 빠르게 풀었지만 메모리 초과...
기존의 BFS 문제의 경우 상하좌우 최대 4가지 분기로만 나눠졌기 때문에 메모리 초과 문제가 안났지만
이번 문제는 연결된 노드의 개수만큼 큐에 저장되기 때문에 케이스에 따라 메모리 초과가 날 수 있다는 것을 고려해야했다.
BFS문제에서 메모리 초과가 날 경우
-> DP를 첨가해서 풀면 맛이 좋다
from collections import deque
def bfs(cls, target):
q = deque([(0, target)])
while q:
coin_cnt, now = q.popleft()
for c in cls:
if now - c > 0 and dp[now-c] > coin_cnt + 1:
dp[now-c] = coin_cnt + 1
q.append((coin_cnt+1, now - c))
elif now - c == 0:
return coin_cnt + 1
return -1
N, K = map(int, input().split())
coin_ls = []
dp = [int(1e9) for _ in range(K+1)]
for _ in range(N):
n = int(input())
if n not in coin_ls:
coin_ls.append(n)
print(bfs(coin_ls, K))
참고자료
https://campkim.tistory.com/15
백준 동전 2294 BFS 파이썬 문제풀이
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연
campkim.tistory.com
'코딩테스트' 카테고리의 다른 글
| [백준 파이썬 1948번 임계경로] 위상정렬 응용과 역추적의 활용 (1) | 2023.10.25 |
|---|---|
| [백준 파이썬 1432번 그래프 수정] 생각의 전환의 전환 with 위상정렬 (0) | 2023.10.25 |
| [백준 파이썬 2617번 구슬 찾기] 재귀함수와 동적계획법 DP (2) | 2023.10.23 |
| [백준 파이썬 21606번 아침 산책] 메모리 초과 해결 (0) | 2023.10.20 |
| [백준 파이썬 13334번 철로] heapq의 활용 (2) | 2023.10.17 |