BOJ 1422. 숫자의 신

 

문제 링크

 

문제 풀이

 이 문제는 $K \leq 50$개의 자연수 중에서 $N\space\space(K \leq N \leq 50)$개의 자연수를 중복을 허용하고 뽑아 이어붙였을 때 만들어질 수 있는 가장 큰 수를 출력하는 문제이다. 이 때 주어진 K개의 자연수 모두 적어도 한 번씩은 사용되어야한다. 

 

 이 문제를 접근할 때 두 가지를 고려하였다. 첫 번째는 주어지는 각 숫자의 사용 개수이고, 두 번째는 숫자들의 사용 순서이다. 먼저 각 숫자의 사용 개수는 당연히 자릿수가 가장 많은 숫자를 많이 사용하는 것이 유리하다. 왜냐하면 자릿수가 많을수록 숫자가 커지기 때문이다. 그래서 자릿수가 가장 큰 숫자를 $N-K$번 사용하고 나머지를 1번씩만 사용할 생각을 하였다. 만약 자릿수가 가장 큰 숫자가 2개 이상이라면 더 큰 숫자를 사용하는 것이 좋다는 것도 자명하다.

 

 두 번째는 사용 순서인데 조금만 생각해보면 맨앞자리가 큰 수 일 수록 먼저 사용하는 것이 좋다는 것을 알 수 있다. 예를 들어 22 9 8 5가 있으면 98522와 같이 앞의 자리가 큰 숫자들을 앞쪽에 배치하는 것이 좋다. 그런데 까다로운 것은 맨 앞자리수가 같은 수들이다. 여기에는 두 가지 경우가 있다.

 

Case 1) 다른 자릿수가 존재하는 경우 $(ex. 3151, 31842)$

  예시처럼 뒤에 있는 숫자들이 차이가 나면 최초로 더 큰 수가 나온 수가 더 좋다. 이 경우에서는 5와 8을 비교했을 때 31842를 사용하는 것이 3151을 사용하는 것보다 유리하다.

 

Case 2) 다른 자릿수가 존재하지 않는 경우 $(ex. 7811, 78)$

   이런 경우에서는 78까지 모두 똑같기 때문에 Case1처럼 비교할 수 없다. 그런데 직관적으로 생각해보면 781178으로 쓰는 것보다 787811로 쓰는 것이 더 크다. 즉 11과 78을 비교했을 때 78이 더 크기 때문에 이 경우에선 78을 먼저 쓰는 것이 좋다.

 

이를 수식적으로 정리해서 적어보자. 먼저 함수 $f(N_1,N_2)$을 $N_1$이 먼저 오는 게 유리할 때 1 true, $N_2$가 먼저 오는게 유리할 때 0 false를 반환하는 함수로 정의하자.$$let) f(N_1,N_2) := \begin{cases}true & when\space N_1\space comes\space first\\false & when\space N_2\space comes\space first\end{cases}$$

 

추가적으로 $N_1$과 $N_2$의 자릿수 개수를 각각 $l_1,\space l_2$로 정의하자.

$$let) l_1 :=(number\space of\space digits\space in\space N_1)$$$$let) l_2 :=(number\space of\space digits\space in\space N_2)$$

 

일반성을 잃지 않고 $l_1 \geq l_2$라고 가정하고, $i$라는 인덱스를 $N_1[i] \neq N_2[i],\space\space i<l_2$을 만족하도록 하는 최초의 인덱스라고 하자. 그러면 함수 $f$는 다음과 같은 값을 가진다.$$f(N_1,N_2) = \begin{cases}N_1[i] > N_2[i] &if \space\space\space^\exists i\\f(N_1[l_2]...N_1[l_1-1],N_2) & if\space\space\space ^\nexists i \end{cases}$$

 

 이를 바탕으로 코드를 짜면 된다. 여기서 $f$라는 함수를 기준으로 주어진 $K$개의 숫자들을 정렬하고 순서대로 출력하면된다. 특히 자릿수가 가장 많은 숫자는 $N-K$번 출력해줘야한다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int K,N,mxLength = 0;
vector<string> leadingDigit[10];
string longestNum;

bool compareNum(string num1, string num2){
    int l1 = num1.length();
    int l2 = num2.length();
    if(num1 == num2) return true;
    if(l1 == l2){
        for(int i=0;i<l1;i++){
            if(num1[i] > num2[i]) return true;
            if(num1[i] < num2[i]) return false;
        }
    } else if(l1 > l2){
        for(int i=0;i<l2;i++){
            if(num1[i] > num2[i]) return true;
            if(num1[i] < num2[i]) return false;
        }
        return compareNum(num1.substr(l2), num2);
    } else return !compareNum(num2,num1);
}

void input(){
    cin>>K>>N;
    for(int i=0;i<K;i++){
        string num;
        cin>>num;
        leadingDigit[num[0] - '0'].push_back(num);
        if(mxLength < num.length()){
            mxLength = num.length();
            longestNum = num;
        } else if(mxLength == num.length()){
            if(compareNum(num, longestNum))longestNum = num;
        }
    }
}

void solve(){
    for(int i=1;i<=9;i++){
        if(leadingDigit[i].empty()) continue;
        sort(leadingDigit[i].begin(),leadingDigit[i].end(),compareNum);
    }
    bool flag = true;
    for(int i=9;i>=1;i--){
        if(leadingDigit[i].empty()) continue;
        for(int j=0;j<leadingDigit[i].size();j++){
            if(flag && leadingDigit[i][j] == longestNum){
                for(int k=0;k<=N-K;k++) cout<<longestNum;
                flag = false;
            } else {
                cout<<leadingDigit[i][j];
            }
        }
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    input();
    solve();
}