백준 1082 - 방 번호

www.acmicpc.net/problem/1082

 

가지고 있는 돈으로 만들 수 있는 가장 큰 수를 출력해야 한다.

 

0을 제외하고 0으로 시작하는 수가 없다고 한다.

 

이 문제는 양의 정수와 관련하여 다음과 같은 성질을 생각할 수 있다.

 

1. 자릿수가 많을수록 큰 수이다.

 

2. 어떤 두 수를 비교할 때 자릿수가 같다면 가장 앞에 자리가 큰 수가 더 크다.

 

이 두 성질을 통해 이 문제의 최적해를 구하기 위해서는 첫번째 숫자가 0이 되서는 안된다는 규칙을 지키면서 자릿수를 가능한한 크게 늘려야 하고, 자릿수를 늘릴 수 없다면 그 상태에서 수를 가장 크게 만들어야 한다.

 

이는 가장 싼 가격의 숫자를 최대한 많이 사서 자릿수를 늘리고 (첫번째 숫자는 0이 될 수 없다는 규칙을 지키면서) 자릿수를 최대한 늘리고 남은 나머지 돈으로 앞의 자리 숫자부터 최대한 큰 걸로 바꾸는 탐욕적인 방법으로 해결할 수 있다.

 

 

주어진 제한사항에 유의하여 trivial case를 세우고 방법을 구현하기만 하면 문제를 해결할 수 있다.

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
 
int num_fee[10];
 
int main()
{
    memset(num_fee, -1, sizeof num_fee);
    ios::sync_with_stdio(false);
    
    int n; cin >> n;
    vector<pii> v(n);
    
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        num_fee[i] = x;
        v[i] = {x, i};
    }
    
    sort(v.begin(), v.end());
    
    int seed;
    cin >> seed;
    
    string res("");
    
    int idx = 0;
    
    if (!v[idx].second)
    {
        if (v.size() == 1 || v[idx + 1].first > seed)
        {
            cout << 0;
            return 0;
        }
        ++idx;
    }
    
    res.push_back(v[idx].second + '0');
    seed -= v[idx].first;
    idx = 0;
 
    while (seed - v[idx].first >= 0)
    {
        res.push_back(v[idx].second + '0');
        seed -= v[idx].first;
    }
    
    for (int i = 0; i < res.size(); ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            if (num_fee[j] == -1)
                continue;
            
            int cur = res[i] - '0';
            
            int diff = num_fee[j] - num_fee[cur];
            if (seed - diff >= 0 && cur < j)
            {
                seed -= diff;
                res[i] = char(j + '0');
            }
        }
    }
    
    cout << res;
}