2294. 동전
by 브이담곰
https://www.acmicpc.net/problem/2294
✔ 유형 : DP
✔ 문제 풀이: 여러개의 하위 문제를 먼저 푼후 그 결과를 쌓아올려 주어진 문제를 해결한다.
메모- 처음에 DFS로 풀었는데, 메모리 초과나서 방법을 찾다가 DP를 공부하고 DP로 풀었다. 근데 이게 정답인듯!!!
DP 풀이
1. 테이블 정의
D[i] = K 로 만들기 위해 필요한 연산 횟수의 최소값
2. 점화식
D[15] = D[14] + 1 ( 1을 더한 이유는 D[15-1]에 1을 더하는 연산 한번을 더하면 D[15]이기 때문)
D[15] = D[9] + 1 ( 1을 더한 이유는 D[15-6]에 5를 더하는 연산 한번을 더하면 D[15]이기 때문)
D[15] = D[3] + 1 ( 1을 더한 이유는 D[15-11]에 11를 더하는 연산 한번을 더하면 D[15]이기 때문)
일반화 하면
D[K] = D[K- coinvalue] + 1
3. 초기값
D[0] = 0
0원이 되기 위한 최솟값은 0번면 된다.
⬇️ 풀이
import sys
from collections import deque
input = sys.stdin.readline
# 입력
n, k = map(int,input().split())
coins = set()
for _ in range(n):
coins.add(int(input()))
dp = [1e9] * (k + 1)
dp[0] = 0
for i in range(1,k+1):
for coin in coins:
if i - coin >= 0 :
dp[i] = min(dp[i] , dp[i-coin] + 1)
# 결과 출력
if dp[k] == 1e9:
print(-1) # k원을 만들 수 없는 경우
else:
print(dp[k])
# 메모리 초과 개빡치네"?
# 참고문제
# https://www.acmicpc.net/problem/1463
'Coding Test > Baekjoon' 카테고리의 다른 글
3055. 탈출 (0) | 2024.07.18 |
---|---|
2665. 미로 만들기 (0) | 2024.07.18 |
2637. 장난감 조립 (0) | 2024.07.18 |
1707. 이분 그래프 (1) | 2024.07.18 |
11725. 트리의 부모 찾기 (0) | 2024.07.18 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰