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$를 구하는 것이다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 정수 $n$과 $k (1 \le n \le 10; 1 \le k \le 10^9)$ 이 주어진다.

각 테스트케이스의 두번째 줄에는 $n$개 정수가 주어진다. $a_1, a_2, ..., a_n (0 = a_1 < a_2 < ... < a_n \le 9)$

Output
정수 $k$에 대해서 화폐 개수가 $k$ 혹은 그보다 작은 화폐 개수로 낼 수 없는 최소 양수 $s$를 출력한다.

Example
input
4
3 13
0 1 2
2 777
0 4
3 255
0 1 3
10 1000000000
0 1 2 3 4 5 6 7 8 9

output
59
778
148999
999999920999999999

문제 접근

사용한 알고리즘: 구현, 정수론, 그리디 알고리즘
걸린 시간 : 00:11
풀 것 같을 듯 말듯 하면서 결국 못푼 문제이다. 하지만 이 문제는 다음에는 꼭 풀 수 있을 것이라고 자신을 가진 문제이다. 문제 설명 시작해보자.

결국 $f(s) > k$를 만족하는 $s$를 구해야 하기 때문에 우리가 구해야할 숫자는 화폐 개수가 $k + 1$를 만족하는 최소 숫자 $s$를 구하는 것이다. 최소 숫자를 구하기 위해서는 높은 자릿수가 최대한 작아야 한다. 즉 낮은 자릿수에서 최대한 많은 화폐를 사용해야 높은 자릿수에서 최소 화폐수를 사용할 수 있다는 것이다. 즉 이것도 그리디 알고리즘을 사용한 문제이다. 낮은 자릿수에서 최대한 많은 화폐를 사용하기 위해서는 어떻게 해야할까? 주어진 수열이 $1, 100, 1000$ 이라면 $1$원으로 만들 수 있는 최대 화폐 수는 $99$개이다. 왜냐하면 $1$원이 $99$을 넘어가면 $100$원 화폐로 그 가격을 지불 할 수 있기 때문에 오히려 낼 수 있는 화폐수가 줄어들게 된다. 그렇기 때문에 수열이 $a_i, a_{i + 1}$ 이런식으로 되어 있다면 최대 지불할 수 있는 화폐 개수는 $a_{i + 1} / a_i - 1$ 개이다.

예를 들어보자. $256$개의 화폐를 지불해야하고, 주어진 화폐는 $1, 10, 1000$이다. 그렇다면 먼저 1의 자리 숫자에서 최대로 지불 할 수 있는 화폐수는 $9$개 이고, 그 다음에는 $99$개이다. 이때 각 반복문마다 최대 지불 할 수 있는 화폐 수보다 현재 남아있는 화폐수가 많다면 $a_{i + 1} / a_i - 1$ 이 값을 현재 자릿수에 곱하고, 그렇지 않다면 현재 남아있는 $k$를 자릿수에 곱하고 반복문을 종료한다. 이때 반복문을 종료했는데, $k$가 남아있다면 맨 마지막 자릿수에 다 곱해서 답을 구한다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll n, k; cin >> n >> k;
        ll arr[n];
        for(auto &x : arr){
            cin >> x;
            ll res = 1;
            while(x--) res *= 10;
            x = res;
        }

        k++;
        ll ans = 0;
        for(int i = 0; i < n - 1; i++){
            ll tmp = min(arr[i + 1] / arr[i] - 1, k);
            ans += arr[i] * tmp;
            k -= tmp;
        }
        if(k > 0) ans += arr[n - 1] * k;
        cout << ans << "\n";
    }
    return 0;
}