백준 11883 - 생일수 I

백준 11883 - 생일수 I

풀이

N이 $10^6$ 이므로 미리 dp배열에 전처리 해놓는다.
이때 dp배열을 string으로 하면 매번 비교하고 문자열을 만드는데 최악의 경우 33333길이가 되므로 $10^6 \times 33333$ 이므로 시간초과가 된다.

따라서 array<int,3>를 이용해서 {3의 갯수, 5의 갯수, 8의 갯수} 이런 식으로 저장하고 마지막에 출력할 때는 3,5,8 순으로 출력하면 가장 작은 생일수가 된다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For_IMPL(condition, i, a, b, increment, decrement) \
    for (ll i = (a); condition; (a < b ? increment : decrement))
#define For(i, a, b) For_IMPL((a < b ? i <= b : i >= b), i, a, b, ++i, --i)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

const int mxn = 1e6+1;
array<int,3> dp[mxn];

array<int,3> operator+(const array<int,3> &a, const array<int,3> &b) {
    return {a[0]+b[0], a[1]+b[1], a[2]+b[2]};
}

void Min(array<int,3> &a, const array<int,3> &b) {
    int asum = a[0]+a[1]+a[2], bsum = b[0]+b[1]+b[2];
    if(asum > bsum) a=b;
    else if(asum == bsum) {
        if(a[0] > b[0]) return;
        if(a[0] < b[0]) a = b;
        if(a[1] > b[1]) return;
        if(a[1] < b[1]) a = b;
        if(a[2] > b[2]) return;
        if(a[2] < b[2]) a = b;
    }
}
string array_to_string(array<int,3> &x) {
    string ret = "";
    vector<char> ch = {'3','5','8'};
    For(i,0,2) {
        ret += string(x[i],ch[i]);
    }
    return ret;
}

void pre() {
    For(x,1,mxn-1) dp[x] = {mxn,mxn,mxn};
    dp[3] = {1,0,0}, dp[5] = {0,1,0}, dp[8] = {0,0,1};
    dp[6] = {2,0,0};
    For(x,9,mxn-1) {
        Min(dp[x], dp[x-3] + array<int,3>{1,0,0});
        Min(dp[x], dp[x-5] + array<int,3>{0,1,0});
        Min(dp[x], dp[x-8] + array<int,3>{0,0,1});
    }
}

void solve() {
    int n; cin >> n;
    if(dp[n] == array<int,3>{mxn,mxn,mxn}) cout << "-1\n";
    else cout << array_to_string(dp[n]) << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
    cin >> TC;
    pre();
    For(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}