동전교환

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

각 단위의 동전은 무한정 쓸 수 있다.

 

▣ 입력설명

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다.

두 번째 줄에는 N개의 동전의 종 류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.

각 동전의 종류는 100원을 넘지 않는다.

 

▣ 출력설명

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

 

▣ 입력예제

3

1 2 5

15

 

▣ 출력예제

3

---

나의 첫번째 코드

#나의 첫번째 코드
def DFS(cnt, cur_sum):
    global min_result
    #동전의 합이 이미 목표치를 넘겼다면
    if cur_sum > M:
        return
    #동전의 갯수가 이미 최소값보다 크다면
    if cnt > min_result:
        return
    #하나의 경우의 수가 나왔다면
    if cur_sum == M:
        if cnt < min_result:
            min_result = cnt
    #아직 동전의 합이 목표치가 안됐고, 가지치기 당할 다른 조건도 충족안됨: 계속 탐색
    else:
        for x in coins:
            DFS(cnt+1, cur_sum+x)


if __name__ == "__main__":
    N = int(input())
    coins = list(map(int, input().split()))
    M = int(input())
    min_result = 2147000000
    DFS(0,0)
    print(min_result)

 

나의 두번째 코드 -> 성공!

#나의 두번째 코드 -> 성공!
def DFS(cnt, cur_sum):
    global min_result
    if cnt > min_result:
        return
    if cur_sum > M:
        return
    if cur_sum == M:
        if cnt < min_result:
            min_result = cnt
    else:
        for x in coins:
            DFS(cnt+1, cur_sum+x)

if __name__ == "__main__":
    N = int(input())
    coins = list(map(int, input().split()))
    coins.sort(reverse=True)
    M = int(input())
    min_result = 21476000000
    DFS(0,0)
    print(min_result)

 

모범답안

#모범답안
def DFS(L, sum):
    global res
    if L>res:
        return
    if sum>m:
        return
    if sum==m:
        if L < res:
            res = L
    else:
        for i in range(n):
            DFS(L+1, sum+a[i])

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    res = 2147000000
    a.sort(reverse=True)
    DFS(0,0)
    print(res)

 

느낀점

1. 첫번째 코드 결과, 테스트 케이스 두 개에서 타임오버가 나왔다..
가지치기를 더 해보자! 동일한 조합이지만 순서가 다른 경우를 전부 세서 오래걸리는것같으니
그 부분을 고쳐볼까!

2. 그냥 큰 동전부터 시도하는걸로 sort사용해서 바꿨더니 아주.빨라졌다 헤헤
이렇게 하면 안될거같긴한데..ㅋ.ㅋ.풀리면 됐지머  모범답안이나 봐야겠다.
큰 동전부터 시도하면 cnt가 min_result보다 커지면 바로 return되는 경우가 훨씬 빨리 오니까
시간 효율성이 훨씬 좋아진것같다. 아니근데 잘한거같은데?!!

3. 아니 진짜루 잘했네. 모범답안이랑 완저니 똑같이 풀었다. 
가지치기 경우도 정확히 똑같이 골라냄.
물론 어려운 문제는 아니었지만.. 아냐 그런생각하지마 암튼 넘 잘해땅!!!

 

다시 써보기

#다시 써보기
input = sys.stdin.readline
def DFS(cnt, cur_sum):
    global result
    if cnt > result:
        return
    if cur_sum > M:
        return
    if cur_sum == M:
        if cnt < result:
            result = cnt
    else:
        for x in coins:
            DFS(cnt+1, cur_sum+x)

if __name__=="__main__":
    N = int(input())
    coins = list(map(int, input().split()))
    M = int(input())
    coins.sort(reverse=True)
    result = 2147000000
    DFS(0,0)
    print(result)