개발새발 로그

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전 0 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 119991 63272 48664 51.972% 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오...

그리디 알고리즘은 "지금 당장 눈앞에 보이는 최적의 상황만을 쫒는 알고리즘"이다. 그리디 알고르짐은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있습니다. 또한 특정한 상황에는 그리디 알고리즘이 최적의 해를 구할 수도 있습니다. 예제로 거스름돈 문제를 풀어보겠습니다. 예를 들어 670원을 걸러줘야하는 상황입니다. 이는 10원짜리 67개보다 500원짜리 1개 50원짜리 1개 10원짜리 1개를 주는 것이 총 3개로 더 효율적입니다. 따라서 이 경우 "무조건 더 큰 화폐 단위부터 거슬러준다"라는 알고리즘만 지키면 최적의 해를 구할 수 있습니다. 이러한 그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, ..