3687 성냥 개비

Link

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

Detail

문제를 해결하기 위한 핵심 개념은 “자릿수”다. 최대값은 최대한 적은 성냥개비로 숫자개수 뻥튀기를, 최솟값은 최대한 많은 성냥개비로 숫자개수를 줄이는 것이 메인 아이디어.

가장 적은 막대가 드는 숫자는 1로, 2라는 깔끔한 개수를 가진다. 홀수는 711111… 로, 짝수는 1111… 로 최대한 많은 숫자를 가지는 것이 좋다.

최솟값을 구하기 위해서, 가장 많은 막대를 사용하는 숫자는 8(7개)다. 하지만 자릿수만 맞춰서는 일부 반례가 존재한다.

대표적으로 막대가 17개라면, 8을 최대한 욱여넣을때 788 이라는 결과가 나오지만, 268 이라는 결과값을 뽑을 수 도 있다.

따라서 자릿수만을 구하고, 해당 자릿수와 막대 개수를 만족하는 최소값을 Dp로 구해주는 방식을 채택했다.

Code

 
#include<bits/stdc++.h>  
  
  
#define LL long long int  
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);  
#define IMPOSSIBLE (-100)  
  
using namespace std;  
  
// StickCost[n] = n을 만드는데 필요한 막대의 개수  
int StickCost[10] = {6,2,5,5,4,5,6,3,7,6};  
vector<vector<LL>> Dp;  
  
  
void print_max(int n) {  
    // 정답은 항상 n / 2자릿수의 숫자  
    // n이 홀수일 경우, 7111... 형식  
    // n이 짝수일 경우, 1111... 형식  
    if(n % 2 == 0) {  
       for(int i = 0; i < n / 2; i++) {  
          cout << "1";  
       }  
    } else {  
       cout << "7";  
       for(int i = 0; i < n / 2 - 1; i++) {  
          cout << "1";  
       }  
    }  
}  
  
// len: 현재 자릿수  
// n: 남은 막대의 개수  
// is_first: 맨 왼쪽 숫자인지 구분을 위한 트리거  
LL get_min_num(int len, int n, bool is_first = false) {  
    if(len == 1) {  
       for(int i = 0; i < 10; i++) {  
          if(is_first and i == 0) continue;  
          if(n - StickCost[i] == 0) {  
             return i;  
          }  
       }  
  
       return IMPOSSIBLE;  
    }  
  
    if(len == 2 and n == 8) {  
       return 10;  
    }  
  
    LL& ret = Dp[len][n];  
    if(ret != -1) return ret;  
  
    ret = LLONG_MAX;  
    for(int i = 0; i < 10; i++) {  
       if(is_first and i == 0) continue;  
  
       if(n - StickCost[i] >= 0) {  
          LL next = get_min_num(len - 1, n - StickCost[i]);  
          if(next == IMPOSSIBLE) continue;  
  
          ret = min(ret, (LL)i * (LL)pow(10, len - 1) + next);  
       }  
    }  
  
    if(ret == LLONG_MAX) ret = IMPOSSIBLE;  
    return ret;  
}  
  
void print_min(int n) {  
    int length = 0;  
    if(n <= 7) length = 1;  
    else {  
       length = n / 7;  
       if(n % 7 != 0) length++;  
    }  
  
    Dp.assign(length + 1, vector<LL>(n + 1, -1));  
  
    LL ret = get_min_num(length, n, true);  
    cout << ret;  
}  
  
void solution() {  
    int n;  
    cin >> n;  
  
    print_min(n);  
    cout << " ";  
    print_max(n);  
    cout << "\n";  
}  
  
int main() {  
    FAST_IO;  
  
    int t_case;  
    cin >> t_case;  
  
    while(t_case--) {  
       solution();  
    }  
  
    return 0;  
}