K원을 만드는데 필요한 동전 개수의 최솟값을 만들기 위해서는 동전의 가치가 큰 동전부터 사용해야 한다동전의 가치가 큰 동전부터 사용하다가 K원에서 현재 동전을 뺐을 때, 0보다 작아진다면 다음으로 가치가 큰 동전을 사용한다using namespace std;int N,

참고 Kruskal Minimum Spanning Tree Algorithm 모든 간선을 가중치의 오름차순으로 정렬 스패닝 트리에 하나씩 추가 가중치가 작다고 무조건 간선을 트리에 더하는 것이 아니라, 사이클이 생기지 않는 경우에만 트리에 더해준다 상호 배타적 집합