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
블로그의 정보
농담곰담곰이의곰담농
브이담곰