[3687]성냥개비

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

3687번: 성냥개비

<문제>

최대는 쉽다, "7111..."혹은 "111..."의 형태중 하나.

최소는 dp로 해결이 가능한데, 6은 원래는 0이지만, 첫자리에 0이 올 수 없으니 dp[6]은 6이다.  

한마디로, dp의 초기값과 기저 사례(db)가 분리되어 있다는 뜻이다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int t, n, base[10] = {2, 5, 5, 4, 5, 6, 3, 7, 6, 6};
ll db[9] = {0, 0, 1, 7, 4, 2, 0, 8, 10};
ll dp[101];
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    int i, j;
    for (i = 0; i < 9; i++) dp[i] = db[i];
    dp[6] = 6;
    for (i = 9; i <= 100; i++) {
        dp[i] = dp[i - 2] * 10 + db[2];
        for (j = 3; j <= 7; j++) {
            dp[i] = min(dp[i - j] * 10 + db[j], dp[i]);
        }
    }
 
    while (t--) {
        cin >> n;
        ll Min = dp[n];
        string Max = "";
        if (n % 2 == 0) {
            for (i = 0; i < (n / 2); i++) Max += '1';
        } else {
            n -= 3;
            Max += '7';
            for (i = 0; i < (n / 2); i++) Max += '1';
        }
 
        cout << Min << " " << Max << '\n';
    }
 
    return 0;
}