[개쉬운 풀이] 백준 3687 성냥개비 CPP (13일차)

문제

 

생각

단순한 DP문제라고 생각했다. 그러나 초기값만 수동으로 설정하는 것이 싫어서 고민하던 도중, 그냥 수동으로 설정하였다.

이때 앞자리가 0이되면 안되는 것을 고려해야한다.

 

1. 작은 수

작은 수는 2~8개 를 사용하면 이렇게 나온다. {0,0,1,7,4,2,0,8,10}

그러나 여기서 앞자리가 0이 될 수 없으므로 6개는 6으로 재초기화한다.

이후 성냥개비는 각각 2~7개 까지 각 숫자에 사용될 수 있으므로 현재 숫자에 2~7개를 뺀 숫자의 dp를 확인하여 숫자를 만들어 나간다.

dp[n] = min(dp[n], dp[n-(성냥개비 가능 갯수)] * 10 + 초기 성냥개비 숫자[성냥개비 가능갯수]) 가 된다.

 

2. 큰 수

패턴을 보면 7과 1로만 이루어진다. 즉 짝수면 1로 시작하고 홀수면 7로 시작하면 된다.

왜냐하면 1과 7은 각각 2와 3개로 이루어져있는데 4개를 사용하는 것 보다 1을 사용하여 두 자리를 차지하는 것이 더 큰 수이다.

 

풀이

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 0 : 6개
// 1 : 2개
// 3 : 5개
// 4 : 4개
// 5 : 5개
// 6 : 6개
// 7 : 3개
// 8 : 7개
// 9 : 6개

const int MAX = 101;
int small_num[9] = {0,0,1,7,4,2,0,8,10};
long long small[MAX];

void make_small_num(){
    for(int i = 1; i < 9; i++){
        small[i] = small_num[i];
    }

    small[6] = 6;

    for(int i = 9; i < MAX; i++){
        small[i] = small[i-2]*10 + small_num[2];
        for(int n = 3; n <= 7; n++){
            small[i] = min(small[i], small[i-n] * 10 + small_num[n]);
        }
    }
}

int main(){
    int t;
    cin >> t;
    make_small_num();
    while(t--){
        int n;
        cin >> n;
        string big;
        if(n%2 == 0){
            big = "1";
            for(int i = 1; i < n/2; i++){
                big = big + "1";
            }
        }
        else{
            big = "7";
            for(int i = 1; i < n/2; i++){
                big = big + "1";
            }
        }
        cout << small[n] << " "<< big << endl;
    }
    return 0;
}