백준. 11047 동전0 | 파이썬, 그리디 알고리즘

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

해설

이 문제는 그리디 알고리즘을 사용한다.

그리디 알고리즘이란, 말그대로 "탐욕적"으로 문제를 해결하는 방식인데,

해결해나가는 과정에서 가장 최선의 선택을 해서 풀어나가는 알고리즘이다.

그렇기 때문에 항상 가장 올바른 답을 도출하지는 않는다. 그러나 속도 면에서 다른 그래프 탐색 알고리즘보다 빠르다는 장점이 있다.

 

준규는 동전을 총 N종류를 가지고 있고, 이 동전들을 사용해서 K원만큼 만들려고 한다.

K원을 만들기 위해서 가장 큰 동전부터 선택해나가면서, K원이 될 때까지 동전을 찾으면 된다.

 

# input을 나란히 받고, int형으로 바꿔준다. ex) 1 19 를 입력하면 N, K에 각각 1 19가 들어감
N, K = map(int, input().split())

coins = sorted([int(input()) for _ in range(N)], reverse=True)

answer = 0
for c in coins:
    if K <= 0:
        break
    if K >= c and K > 0:
        answer += (K//c)
        K -= c * (K//c)
        
print(answer)

N종류의 동전을 입력받은 다음, 내림차순으로 재정렬해준다.

이 때, sorted 함수를 사용하여 reverse를 True로 주면, 내림차순으로 정렬된 리스트를 리턴해준다.

리턴한 값을 coins에 넣으면, 준규가 가지고 있는 동전을 금액이 큰 순서대로 내림차순으로 정렬할 수 있다.

 

coins를 for문으로 반복문을 돈다.

이 때, K가 0보다 작거나 같아지면, 동전을 모두 찾은 것이므로 break를 해준다.

그렇지 않고, K가 c(coins에서 반복하는 값)보다 크고, K가 0보다 크면 K에서 해당 동전의 금액만큼 빼줄것이다.

만약, K가 4200이고 c가 1000이라고 가정하면, c가 4개 있으면 K에서 4000을 뺄 수 있다. 4개는 K에서 c로 나눈 몫이라고 볼 수 있다.

따라서, answer(동전의 개수) 에 K에서 c를 나눈 몫 만큼을 더해주면 된다.

(파이썬에서는 //을 쓰면 몫만 구할 수 있으므로, //를 사용해서 구해줬다.)

그리고 K에서 c * (K // c) 만큼을 빼주면 된다.

 

반복이 끝나면, answer를 print 해주면 최종 답이 나온다.