알고리즘/codeforces
Educational Codeforces Round 116 - C. Banknotes
문제 설명 버클리음대에서는 $n$개 종류의 화폐를 사용하고 있다. $i$번째 타입은 $10^{a_i}$의 가치를 가지고 있다. 즉 첫번째 타입 화폐는 $1$원의 가치를 가지고 있다. $f(s)$를 정확히 $s$원을 내기 위해서 필요한 최소 화폐의 수라고 정의하자. 예를 들면 버클리음대에서 $1, 10, 100$원을 사용한다고 할 때 $f(59) = 14$ 이다. $1$원짜리 화폐 $9$개와 $10$원 짜리 화폐 $5$개로 최소 화폐 수로 $59$원을 낼 수 있기 때문이다. 그리고 이 방법 이외에는 더 적은 수로 화폐를 지불 할 수 없다. 정수 $k$에 대해서 화폐 개수가 $k$ 혹은 그보다 작은 화폐 개수로 낼 수 없는 최소 양수 $s$를 구하자. 즉 $f(s) > k$인 $s$를 구하는 것이다. Inp..
