[백준 1398] 동전 문제 : 수의 규칙성을 이용한 최적화
백준 1398번 : 동전 문제 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 대해서 10^K인 동전과 25*100^K인 동전이 있다. 이기훈은 이 나라에서 새로운 차를 한 대 사려고 한다. 이기훈은 차를 살 때, 가능하면 동전의 개수를 최소로 하려고 한다. 이기훈이 필요한 동전 개수의 최솟값을 www.acmicpc.net 이 문제는 처음 시도할 때 정말 막막했다. 일단 탐욕법으로 생각해보는 것은 바람직하지 않다. 일단 쉽게 생각해볼 수 있는 반례로 30이 있는데, 탐욕법으로 비싼 동전부터 쓰..
