[BOJ/골드5] 동전 2 / 효율적인 화폐구성 (DP/Python)

문제

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

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

입력

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

출력

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

예제 입력 1

3 15
1
5
12

예제 출력 1

3

 

---

문제를 보자마자 어떤식으로 풀어야할지 감이 왔다.

입력받은 모든 coin을 돌려 보며 dp[i-coin]가 가장 작은 것을 찾는 것이었다.

 

1차 도전

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

coins = []
for _ in range(n):
    coins.append(int(input()))

dp = [0] * 100001

for i in range(len(coins)):
    dp[coins[i]] = 1

#dp[1] dp[5] dp[12] = 1

for i in range(1,m+1):
    if dp[i] == 1:
        continue
    minNum = 999
    for coin in coins :
        if i > coin and dp[i-coin] != 0 and minNum > dp[i-coin]+1 :
            minNum = dp[i-coin]+1

    if minNum == 999:
        dp[i] = 0
    else :
        dp[i] = minNum

if dp[m] == 0 :
    print(-1)
else :
    print(dp[m])
            

# 1인 애들을 0으로 만들어 버리는거,

실패. 

아니 모든 테스트 케이스 정확히 돌아가고 질문 검색에 적혀있는 모든 반례까지 다 맞다고 나오는데

계속 35%에서 실패가 나왔다. 

 

2차 도전

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

coins = []
for _ in range(n):
    coins.append(int(input()))

dp = [0] * 100001

for i in range(len(coins)):
    dp[coins[i]] = 1


for i in range(1,m+1):
    if dp[i] == 1:
        continue
    minNum = 100001
    for coin in coins :
        if i > coin and dp[i-coin] != 0 and minNum > dp[i-coin]+1 :
            minNum = dp[i-coin]+1

    if minNum == 100001:
        dp[i] = 0
    else :
        dp[i] = minNum

if dp[m] == 0 :
    print(-1)
else :
    print(dp[m])

 

2차도전이라고 하기도 민망하게

minNum값만 바꿔주었다.

=> 1000원을 만드는 데, 1원만으로 만드는 경우도 분명 있을 것이다. 

 

최솟값을 구하기 위해 잡아놓은 값을 너무 작게 잡아놓아서 계속 틀렸습니다가 나왔당. 

 

---

코드 분석

 

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

coins = []
for _ in range(n):
    coins.append(int(input()))

dp = [0] * 100001

for i in range(len(coins)):
    dp[coins[i]] = 1

초기 값을 입력 받은 후 dp table을 생성한다.

또 초기에 입력받은 동전들에 대한 dp table을 1로 채운다.

 

for i in range(1,m+1):
    if dp[i] == 1:
        continue
    minNum = 100001
    for coin in coins :
        if i > coin and dp[i-coin] != 0 and minNum > dp[i-coin]+1 :
            minNum = dp[i-coin]+1

    if minNum == 100001:
        dp[i] = 0
    else :
        dp[i] = minNum

 

반복문을 돌려서 바텀업 방식으로 DP table을 채워 나갈 것.

 

1. 만약 dp[i]가 1이라면 (=초기 입력값으로 받은 코인) 바로 반복문 탈출

2. 매 반복문 마다 최소인 dp[i-coin] 값을 찾기 위해 minNum 변수 초기화

3. 입력받은 coin들을 모두 돌며 최소값 체크

 

if dp[m] == 0 :
    print(-1)
else :
    print(dp[m])

출력

 

---

반복문 돌면서 min()함수를 쓰는 방법을 생각해보다가 실패하여 이런식으로 코드를 짰다.

인덱스에러가 나지 않을 자신 있으면 이런식으로 짜도 되지만,

더 좋은 코드를 만들어보아야겠다.