BOJ 1082

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

1082번: 방 번호

그리디로 풀어보려다 포기하고 그냥 dp로 풀고 그리디 풀이를 봤다.

그리디 풀이:

1. 가장 값이 싼 숫자를 이어붙여 가장 자릿수가 긴 수를 만든다.

2. 앞 자릿수부터 바꿀 수 있는 가장 큰 숫자로 바꾼다.

 

dp코드

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define _unique(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
const int INF = 1e9;
const ll mod = 998244353;

int n, m;
vector<int> arr;
string dp[55];

string dfs(int cur){
    string &ret = dp[cur];
    if(ret!="-1") return ret;
    ret = "";
    if(cur==m){
        for(int i=1;i<n;i++){
            if(cur>=arr[i]){
                string s = dfs(cur-arr[i]);
                if(ret.size()<s.size()+1){
                    ret = to_string(i)+s;
                }
                if(ret.size()==s.size()+1){
                    ret = max(ret, to_string(i)+s);
                }
            }
        }
    }
    else{
        for(int i=0;i<n;i++){
            if(cur>=arr[i]){
                string s = dfs(cur-arr[i]);
                if(ret.size()<s.size()+1){
                    ret = to_string(i)+s;
                }
                if(ret.size()==s.size()+1){
                    ret = max(ret, to_string(i)+s);
                }
            }
        }
    }
    return ret;
}

void solve() {
    cin>>n;
    arr.resize(n);
    for(auto &i:arr) cin>>i;
    cin>>m;
    for(int i=0;i<=m;i++){
        dp[i]="-1";
    }
    string ans = "";
    if(m>=arr[0]) ans = "0";
    cout<<max(ans, dfs(m));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(0);

#ifndef ONLINE_JUDGE
    freopen("./input.txt", "r", stdin);
    clock_t _st_t = clock();
#endif

    int tt = 1;
    //cin>>tt;
    while(tt--){
        solve();
        cout<<'\n';
    }

#ifndef ONLINE_JUDGE
    cerr << endl << endl << (double) (clock() - _st_t) / (double) CLOCKS_PER_SEC << "sec" << endl;
#endif

    return 0;
}