숫자의 신 (feat. 백준, 1422번)

숫자의 신
https://www.acmicpc.net/problem/1422

1422번: 숫자의 신

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct cmp1{
    bool operator()(const string& v1, const string& v2){
        if(v1.size() == v2.size()){
            return v1 < v2;
        }
        return v1.size() < v2.size();
    }
};
struct cmp2{
    bool operator()(const string& v1, const string& v2){
        return v1 + v2 < v2 + v1;
    }
};
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int K, N;
    string tmp;
    cin >> K >> N;
    priority_queue<string, vector<string>, cmp1> q;
    priority_queue<string, vector<string>, cmp2> ans;
    for(register int k = 0; k < K; ++k)
        cin >> tmp, q.push(tmp);
    for(register int n = K; n < N; ++n)
        q.push(q.top());
    while(!q.empty())
        ans.push(q.top()), q.pop();
    tmp.clear();
    while(!ans.empty())
        tmp += ans.top(), ans.pop();
    cout << tmp;
    return 0;
}
// *&)*@*

 

1. 상당히 어려웠습니다. 반나절은 걸린것 같습니다.
2. 입력받은 자연수는 길이가 길고 사전상 앞순이어야 더 큰값입니다. 따라서 해당 조건에 따라 정렬될 수 있어야 합니다.
3. N개의 자연수는 N0+N1 > N1+N0 순서대로 정렬되어야 합니다. 두 자연수가 합쳐졌을때 더 큰 조건일수록 우선순위가 높아야 합니다.
4. 위 조건들로 정렬된 자연수들을 쭉 나열하면 정답이 됩니다.