https://www.acmicpc.net/problem/1084

설명

보통 최대 자릿수를 찾는 이러한 문제들은 그리디로 푸는 편이다. 우리가 고려할 점은 2가지이다.

  1. 자릿수를 최대로 만든다.
  2. 큰 자릿수부터 큰 수로 교환이 가능하면 교환한다.

일단은 1번부터 고려해보자. 자릿수를 최대로 만들려고 하면 가격이 가장 낮은 숫자로 채우는 것이 좋다는 것은 자명하다. 그렇기에 정렬을 하든 따로 구하든 하여서 만들 수 있는 최대자릿수를 만들자.

이제 2번의 경우는 여러 가지로 나뉜다. 먼저 현재 만들어진 수에서 적절하게 교환한다. 어떻게든 큰 수로 만들어야 하기에 때문에 큰 수부터 순회하면서 현재 남은 가격으로 얼만큼 교환이 가능한지 체크해가면서 교환해간다. 여기서 추가로 고려해야 할 점은, 가장 작은 가격의 숫자가 0이고, 아무것도 교환하지 못했을 때이다. 이때부터는 최대자릿수를 줄여야 하기에, 자릿수를 가장 적게 줄이면서 가장 큰 숫자를 찾으면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,ll> pil;

vector<pil> card;
ll price[10],cnt[10];
ll N,M;

bool compare(pil a,pil b) {
    if(a.second == b.second) return a.first > b.first;
    return a.second < b.second;
}

void PR() {
    ll sum = 0;
    bool zero_only = true;
    for(int i=0; i<N; i++) {
        sum += cnt[i];
        if(i != 0 && cnt[i] != 0) zero_only = false;
    }
    if(zero_only) cout << "1\n0\n0\n";
    else {
        cout << sum << "\n";
        ll bias = min(sum,50LL);
        for(int i=N-1; i>=0; i--) {
            if(bias == 0) break;
            ll count = min(bias,cnt[i]);
            for(int j=0; j<count; j++) cout << i;
            bias -= count;
        }
        cout << "\n";

        bias = min(sum,50LL);
        vector<int> r_ans;
        for(int i=0; i<N; i++) {
            if(bias == 0) break;
            ll count = min(bias,cnt[i]);
            for(int j=0; j<count; j++) r_ans.push_back(i);
            bias -= count;
        }
        for(auto it=r_ans.rbegin(); it!=r_ans.rend(); it++) cout << *it;
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> price[i];
        card.push_back({i,price[i]});
    }
    sort(card.begin(),card.end(),compare);
    cin >> M;

    int minv = card[0].first;
    ll max_radix = cnt[minv] = M/card[0].second;
    M %= card[0].second;
    if(max_radix == 0) cout << 0,exit(0);

    for(int i=N-1; i>minv; i--) {
        ll diff = price[i] - card[0].second;
        if(diff == 0) {
            swap(cnt[minv],cnt[max(minv,i)]);
            break;
        }
        ll inc = min(M/diff,cnt[minv]);
        cnt[i] += inc, cnt[minv] -= inc;
        M -= inc*diff;
    }
    if(cnt[0] == max_radix) {
        int s_idx = -1;
        ll reduced = max_radix+1;
        for(int i=N-1; i>=1; i--) {
            ll val = (price[i] - M)/price[0];
            if((price[i]-M)%price[0] != 0) val++;
            if(val < reduced) s_idx = i, reduced = val;
        }
        if(s_idx != -1) cnt[0] -= reduced, cnt[s_idx]++;
    }
    PR();
    exit(0);
}

여담

구현한번 귀찮다.