컴굥일지

문제 https://www.acmicpc.net/problem/11047 문제 내용 동전을 적절히 사용해서 K원을 만드는 문제이다. 이때 동전의 최소화하여 사용하는 것이 이 문제의 핵심이다. 문제 풀이 이 문제는 greedy한 성격이 있다. 4200원을 만들 때, (1원짜리 4200개) / (100원짜리 420개) / (1000원짜리 4개 + 100원짜리 2개) 등 여러 방법으로 만들 수 있다. 이 경우 (1000원짜리 4개 + 100원짜리 2개)로 4200원을 만드는 것이 동전의 개수를 최소화할 수 있다. 그럼 이 문제를 풀 때 어떻게 해야 할까? 동전의 가치가 큰 것부터 사용하는 방식을 선택하면 된다. 만들려는 K원보다 가치가 작은 동전들 중에서, 그나마 가치가 큰 동전부터 사용하면 된다. 코드 #i..