[백준] 2294 : 동전 2 - Python

Chooooo·2023년 2월 5일

DP gold 백준

알고리즘/백준

목록 보기

37/204

⚽ 동전 2

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

처음 풀 때는 dfs로 (시간초과 뜬 코드)

import sys
sys.stdin = open("input.text", "rt")

n, k = map(int, input().split())
data = []
for _ in range(n):
    data.append(int(input()))

data.sort(reverse = True)

cnt = 2424242424
def DFS(L, sum):
    global cnt
    if L > cnt: # 최소 갯수 넘어가면 더이상 확인할 필요가 없음 Cut Edge
        return
    if sum > k: # 현재까지 총 합이 k를 넘어가도 더 확인할 필요가 없음 Cut Edge
        return 
    if sum == k: #종료조건.
        if L < cnt:
            cnt = L
    else:
        for i in range(n):
            DFS(L+1, sum + data[i])

DFS(0,0)
print(cnt)

⚽ 코멘트

이 문제야 말로 보자마자 상태트리를 떠올렸다. 동전의 개수 n개를 활용하여 k원을 만들어야 하므로 해당 동전을 사용할지 말지 즉 동전마다 2가지 옵션이 있다. 이걸 n번 반복해 나가면서 k원을 만족하면 된다.

이 문제가 그리디로는 안되는 이유는 만약 동전이 1, 2, 5, 8원이 들어온다면 5원의 배수가 존재하지 않기에 다음번 동전 선택 때 영향을 끼친다. 물론 동전이 1,2,4 이렇게 서로 배수 관계를 이룬다면. 무조건 4원부터 사용해보면서 안되면 2원 안되면 1원 이런 식으로 진행할 수만 있다면 그리디로 푸는게 가장 빠르다. 이 문제는 동전의 입력이 어떻게 올 지 모르므로 그리디는 패쓰

아까 하던 얘기를 덧붙여서 각 동전을 매 순간 선택할지 말지를 생각하면 된다. 그런데 Cut Edge를 분명 다 했다고 생각했는데 시간초과가 떴다. 동전의 최소 갯수이므로 동전 리스트를 내림차순으로 바꿨는데도 시간초과이다.

I don’t know …
그냥 이 문제도 DFS로 풀면 안됐었다. 아무리 생각해도 코드는 맞았었다. 결국 dp로 풀었어야 했다는건데 n,k범위가 이렇게 작은데도 안되는 이유를 모르겠다.
어쩃든 테스트 케이스 내가 만들어서 해봐도 정답이 나오긴 한다. 결국 재귀가 너무 많이 돌아서 시간초과가 뜨는 것 같다. 코드는 맞았다고 생각한다…!

dp로 다시 푼 코드

import sys
sys.stdin = open("input.text", "rt")
n, k = map(int, input().split())
data = []
for _ in range(n):
    data.append(int(input()))

#동전의 최대 값 k == 10000 이걸 맥스로 dp 사용
max_val = 10001
dp = [max_val] * (k + 1)
dp[0] = 0 #처음부터 알 수 있는 값
#dp[n]은 동전 리스트에서 n원을 만들었을 때 최소가 되는 동전의 개수


for x in data:
    for i in range(x, k+1):
        if dp[i] > 0: #값을 가지고 있어야 판단
            dp[i] = min(dp[i-x]+ 1, dp[i])

if dp[k] == max_val:
    print(-1)
else:
    print(dp[k])