농담곰담곰이의곰담농

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

 

블로그의 프로필 사진

블로그의 정보

농담곰담곰이의곰담농

브이담곰

활동하기