백준 11047번 - 동전 0

 

 

* 문제 링크

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

 

 

 

문제 내용 요약

 

동전이 N 종류 있는데, 얘네들 중에 아무 2개를 선택해도 한 동전의 값이 다른 동전의 값의 배수다.

 

이거로 K원을 만드는데 필요한 동전 개수의 최솟값을 구해라. ( 1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000 )

 

 

 

 

 

 

접근법 (그리디 알고리즘이 무엇인가)

 

 

단계별로 풀어보기 '그리디 알고리즘'의 첫 번째 문제.

 

'그리디 알고리즘' 이라는 것은 개념적으로는 별거 없다.

 

대충 "현재 상황에서 최대한 욕심을 부리는 방향으로 선택해도 모든 상황이 최적으로 해결되는 문제"

 

정도로 생각하면 된다.

 

 

그리고 덕분에 나는 어떤 문제가 "그리디 알고리즘" 인지 판단을 잘 못한다.

 

나름대로 욕심 그득그득 방법으로 해도 "그리디 알고리즘" 이 아닌 경우가 있는 것 같아서 말이다.

 

 

 

그래서 어떤 방법이 욕심 그득그득한 방법인가?

 

 

 

현실에서 47600원이 나왔다고 하자.

 

보통은 50000원 내고 거스름돈 받거나 카드를 긁겠지만

 

딱 맞춰 낸다고 하면 10000원짜리 4장, 5000원 1장, 1000원 2장, 500원 1장, 100원 1장 순으로 낼 것이다.

 

10원짜리 4760개를 내면 욕은 먹지만 법적으로 문제가 없어서 실제로 문제가 된 경우가 있다고 한다.

 

 

 

어쨌든 가장 값이 큰 화폐부터 순서대로 맞추는 것이 가장 적게 내는 방법이라는 것을 알 것이다.

 

동전의 가치는 오름차순으로 주어지므로, 뒤에서부터 하나씩 계산해주면

 

어렵지 않게 답을 구할 수 있다.

 

 

 

 

 

 

내 코드

#include <iostream>
using namespace std;

int coin[11];

int main()
{
   int n,m,sum=0;
   scanf("%d %d",&n,&m);
   for(int i=0;i<n;i++) {
       scanf("%d",&coin[i]);
   }
   for(int i=n-1;i>=0;i--) {
       sum+=m/coin[i];
       m%=coin[i];
   }
   cout<<sum;
   return 0;
}

 

 

 

 

 

여담

 

이 문제가 "동전 0" 인 것은 이유가 있다.

 

원래 "동전 2" 문제가 동전의 가치가 배수가 아닌 아무 가치를 지니기 때문에

 

'그리디 알고리즘' 으로는 틀린 케이스가 존재하기 때문이다.

 

그래서 난이도를 낮춰서 내어 "동전 0"일 것이다.

 

사용하는 알고리즘도 '다이나믹 프로그래밍' 으로 다르다.

 

참고로 '동전 1'은 돈을 내는 방법의 가짓수다. 이 또한 DP.

 

나중에 그 두 문제들도 올리지 않을까

 

 

그리고 나는 아직도 부루마블에 왜 2만원짜리가 존재하는지 그 이유를 모른다.