[BOJ] 2294번: 동전 2 (DP)

 

 

 

코드 링크

https://www.acmicpc.net/problem/2294

 

 

 

TIL

• 문제에서 요구하는 것이 사용한 동전의 최수 개수이므로 dp도 그걸 기준으로 저장해야됨!!!
• dp는 tabulation이 더 편하고 생각보다 느리지 않아서 그냥 써도 될 듯 ,,, 
• 항상 edge case랑 변수 범위 생각 하기 !!!!!!!
• 제발 기억해 (dp 최소값 구하는 방법 중 하나)
  • dp[i] = min(dp[i], dp[i-coin]+1)

 

[ 처음에 인덱스 에러난 코드 ]

n, k = map(int, input().split())

dp = [100001]*(k+1)
coins = [int(input()) for _ in range(n)]
for c in coins:
    dp[c] = 1


for coin in coins:
    for i in range(coin, k+1):
        dp[i] = min(dp[i], dp[i-coin]+1)

print(dp[k] if dp[k]<10001 else -1)

• k가 주어진 동전보다 작을 수도 있음
  • 따라서 Outbound 오류 발생

 

 

Code

n, k = map(int, input().split())

dp = [100001]*(k+1)
coins = [int(input()) for _ in range(n)]
for c in coins:
    if c <= k:
        dp[c] = 1

for coin in coins:
    if coin <=k:
        for i in range(coin, k+1):
            dp[i] = min(dp[i], dp[i-coin]+1)

print(dp[k] if dp[k]<10001 else -1)