728x90
SMALL
백준 11047
-
백준. 11047 동전0 | 파이썬, 그리디 알고리즘IT/알고리즘 해설 2021. 10. 28. 00:31
문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 해설 이 문제는 그리디 알고리즘을 사용한다. 그리디 알고리즘이란, 말그대로 "탐욕적"으로 문제를 해결하는 방식인데, 해결해나가는 과정에서 가장 최선의 선택을 해서 풀어나가는 알고리즘이다. 그렇기 때문에 항상 가장 올바른 답을 도출하지는 않는다. 그러나 속도 면에서 다른 그래프 탐색 알고리즘보다 빠르다는 장점이 있다. 준규는 동전을 총 N종류를 가지고 있고, 이 동전들을 사용해서 K원만큼 만들려고 한다. K원을 만들기 위해서 가장 큰 동전부터 선택해나가면서, K원이 될 때까지 동전을 찾으면 된다...