백준 2294_동전2

동전2(백준 2294)

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

DP 방식으로 풀었다
dp[0] = 0 으로 내버려 두며,
나머지 dp는 k만큼 생성 후, inf 값으로 초기화하였고,
현재 반복문의 값을 ‘동전’으로 표현이 가능하다면,
동전 값을 그 이전의 index 값만큼 당긴 뒤, + 1 해준 방식을 하였다
dp를 다 돈뒤
의 dp[k] 값이 math.inf 라면 현재 주어진 동전으로 표현이 불가능하므로
-1을 출력하였다

작은 동전부터 정렬 하였고, 중복값을 없애주었다
bottom - up 방식이라 생각한다

Code

import sys
from collections import deque
import math

inp = sys.stdin.readline

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

coin = [0 for i in range(n)]

for i in range(n):
    coin[i] = int(inp().strip())

coin = list(set(coin))    # 중복요소 제거
coin.sort()

dp = [0] + [math.inf] * k

for i in range(len(coin)):
    for j in range(k + 1):
        # j가 현재 동전값보다 크므로, 표현이 가능
        if j >= coin[i]:
            # 맨 처음 배열(dp[0] = 0) 이므로, 0 + 1 이 dp에 들어오게 된다
            # 이후 돌면서 점점 dp 배열이 업데이트 됨
            dp[j] = min(dp[j], dp[j - coin[i]] + 1)

if dp[k] == math.inf:
    print(-1)
else:
    print(dp[k])

해결 아이디어

1. dp 배열 생성후, 0번째는 0으로 내버려둔 후
   math.inf를 통해 초기화
2. 반복문을 돌며 현재 j 값을 현재 동전으로 표현할 수 있다면
   dp[j] 를 업데이트 해준다
3. 모든 동전 값을 통하여, dp 배열을 업데이트 한 후,
   dp[k]가 math.inf인지 체크하고 -1 혹은 dp[k]를 출력한다