6.7 동전 교환-Cut Edge Tech

문제

동전교환

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

▣ 입력예제 1
3
1 2 5
15

▣ 출력예제 1
3

 

---

내 풀이(첫번째)

if __name__=="__main__":
    n=int(input()) #동전 종류 개수
    coin_list=list(map(int, input().split()))
    m=int(input()) #거스름돈 액수
    cnt=0
    for i in range(1,n+1):
        cnt+=m//coin_list[-i]
        m=m%coin_list[-i]
        if m==0:
            break

print(cnt)

-DFS를 사용하지 않았다. 따라서 모든 경우를 고려해보지 못하므로 오류가 발생할 여지가 있다

 

두번째 풀이(=강의 답안)

def DFS(v, sum):
    global result
    if result<v:
        return
    if sum==m:
        if result>v:
            result=v
    elif sum>m:
        return
    
    else:
        for i in range(n):
            DFS(v+1, sum+coin_list[i])
if __name__=="__main__":
    result=2147000000
    n=int(input())
    coin_list=list(map(int, input().split()))
    coin_list.reverse()
    m=int(input())
    DFS(0, 0)
    print(result)

-지역 변수 처리

global result 코드를 통해서 전역 변수로 변환하여 처리하므로 local error를 해결했다.

 

-DFS처리

def DFS(v, sum): -->v:동전 개수 sum:그동안의 합계 금액

    global result

    if sum==m: -->코드 돌린 합계가 구하고자 한 거스름돈 총액과 동일할 때

        if result>v:-->동전의 개수가 최소일 때를 구하는 것이 목적으므로 

            result=v    이전의 결과값보다 작을 때 결과값 업데이트

    elif sum>m: --> 거스름돈 총액보다 커지면 의미가 없으므로 커트

        return

    else: 

        for i in range(n):  -->DFS 돌리기

            DFS(v+1, sum+coin_list[i]) 

 

-시간 초과 해결 코드

def DFS(v, sum):

    global result

    if result<v: -->result(이전의 동전 개수 최솟값)보다 v(동전 개수)가 많다면 더이상 코드를 돌릴 의미X

        return