백준 3687 성냥개비 혼내주기

 

dp문제긴 한데... 이런 규칙 찾기 문제는 풀어도 영 뿌듯하지가 않다...

 

최댓값은 홀수인 경우 7 이후에 2마다 1을 추가하고, 짝수인 경우엔 그냥 2마다 1을 추가하면 된다.
최솟값은 숫자별 최소값을 쭉 적어보면 17까지는 예외가 있는데, 18 이후부터는 7 마다 이전 숫자에 8을 더해 만드는 규칙을 찾을 수 있다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int arr[22] = {
    0, 0, 
    1, 7, 4, 2, 6, 8,
    10, 18, 22, 20, 28, 68, 88,
    108, 188, 200, 208, 288, 688, 888
};
int t;

void input() {
    fastio;
    cin >> t;
}

string getMax(int num) {
    string ret = "";

    if(num%2) {
        ret += '7';
        num -= 3;
    }

    while(num) {
        ret += '1';
        num -= 2;
    }

    return ret;
}

string getMin(int n) {
    if(n <= 21) return to_string(arr[n]);
    
    int cnt = 0;
    while(n > 21) {
        n -= 7;
        cnt++;
    }
    string ret = to_string(arr[n]);
    while(cnt--) {
        ret += '8';
    }
    return ret;
}

int main() {
    input();
    
    while(t--) {
        int num; cin >> num;
        cout << getMin(num) << " " << getMax(num) << "\n";
    }
}