파이썬 알고리즘 078 | 동전교환 (냅색 알고리즘)

78. 동전교환(냅색 알고리즘)

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.
▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.
▣ 입력예제 1
3
1 2 5
15
▣ 출력예제 1
3

<내 풀이>

• 처음에는 사실 아무 생각 없이 이전 문제랑 동일하게 해보았는데 여기서는 최솟 개수 구하는 것이므로 min으로 바꾸기만 하면 되지 않나 생각
• 그러나 min으로 하면 당연히 기존 dy[j]들이 다 0이기 때문에 dy가 온통 0으로만 유지
• 그래서 가장 최대개수로 일단 dy들 값 갱신해주고 그 다음에 min해서 나머지들과 비교해주기로 생각
  => 그런데 i==1 로 하면 안됨 if i==min(a) 로 했어야 함, 1 동전이 안나오고 2동전이 가장 조그맣게 나오는 걸로 제시됐으면 틀리는 거임

n=int(input())
a=list(map(int,input().split()))
m=int(input())
a.sort()
dy=[0]*(m+1)
for i in a:
    for j in range(i,m+1) :
        if i==1: #이렇게 설정하면 안된다
            dy[j]=dy[j-i]+1
        else:
            dy[j]=min(dy[j], dy[j-i]+1)
print(dy[m])       
 

(2)

n=int(input())
a=list(map(int,input().split()))
m=int(input())
a.sort()
dy=[0]*(m+1)
for i in a:
    for j in range(i,m+1) :
        if i==min(a):
            dy[j]=dy[j-i]+1
        else:
            dy[j]=min(dy[j], dy[j-i]+1)
print(dy[m])      

<풀이>

• dy[j] : j원 거슬러주는데 사용된 동전의 최소 갯수

if __name__=="__main__":
    n=int(input())
    coin=list(map(int, input().split()))
    m=int(input())
    dy=[1000]*(m+1); #dy를 0이 아니라 크게 설정해놓고
    dy[0]=0 # 꼭 첫번째 애는 0으로 초기화 해주고,, 0을 대체할 수 있는 동전은 없으니
    for i in range(n):
        for j in range(coin[i], m+1):
            dy[j]=min(dy[j], dy[j-coin[i]]+1)
    print(dy[m])

<반성점>

• dy[0] 으로 초기화하지 말고 큰 값으로 초기화 해놓고, dy[0]만 0으로 꼭 지정해줬으면 min으로 바로 비교 가능했음, 나처럼 1 먼저 안했어도.. 그리고 심지어 만약 예시에서 가장 작은 숫자로 1이 안나왔으면 틀리는 거임, 1이 아니고 가장 작은 가치의 동전으로 설정해주었어야 한다 너무 허점이 많다
• dy[0]=0으로 꼭 해놨어야 한다.

<배운 점>

<2차 내 풀이>

=>최소를 구할 때는 dy를 [0]이 아닌 큰 값으로 설정하고
dy[0][0]=0으로만 설정해놓으면 됨

n=int(input())
a=list(map(int,input().split()))
m=int(input())
dy=[50]*(m+1)
dy[0]=0
for i in range(n) :
    for j in range(a[i],m+1) :
        dy[j]=min(dy[j], dy[j-a[i]]+1)
print(dy[m])