[Greedy] BOJ 1422_숫자의 신

문제 링크 : www.acmicpc.net/problem/1422

1422번: 숫자의 신

예전에 풀었던 DP 문제인 '방번호' 문제와 비슷한 맥락의 문제이다.

가장 큰 수를 만들기 위해선, 각 숫자들을 최소 한 번씩 사용해야 하므로 숫자의 앞자리가 큰 순으로 붙여나간다.

각 숫자들을 최소 한 번씩 사용하고 난 뒤, 추가로 사용할 숫자는 가장 큰 수가 될 것이다.

 

즉, 입력으로 들어오는 숫자들을 어떻게 정렬할 것인지가 문제의 핵심이 된다.

추가로 사용할 숫자를 찾는 과정은 단순 int의 정렬로 가능하므로,

숫자들을 최소 한 번씩 사용하는 순서를 정하는 것이 중요하다. 

이 풀이에서는 숫자들을 문자열로 변환하여 비교한다.

 

두 수 a, b가 있을 때 어떤 수가 먼저 붙어야 할까?

처음에는 자릿수별로 비교하는 등의 방법을 생각하고 헤맸지만 결론은 간단하다.

두 수를 ab의 형태로 붙인 수와 ba의 형태로 붙인 수를 비교해 더 큰쪽의 순서를 취하는 것이다.

예를 들어 288과 28이 있을 때, 288|28 > 28|288 이므로 288이 더 상위 순서가 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> p;
 
int n, k;
vector<string> high_digit;
int longest = 0;
 
int getfirst(int n) {
    //n의 첫번째 숫자를 반환
    string nstr = to_string(n);
    return nstr[0] - '0';
}
 
bool compare(int a, int b) {
    return a > b;
}
 
bool compare_s(string a, string b) {
    return a + b > b + a;
}
 
void init() {
    string input;
    cin >> n >> k;
 
    for (int i = 0; i < n; i++) {
        cin >> input;
        high_digit.push_back(input);
        int n_input = atoi(input.c_str());
        if (longest < n_input) longest = n_input;
    }
 
    sort(high_digit.begin(), high_digit.end(), compare_s);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    bool flag = false;
    string answer = "";
 
    init();
    int additional = k - n;    //최소 할당량을 제외한  추가 횟수
 
    //가장 수치가 높은 숫자 순서로 붙임
    //가장 긴 숫자와 앞자리 숫자가 일치할 때 그 숫자를 additional 만큼 붙임
    for (int i = 0; i < high_digit.size(); i++) {
        string h = high_digit[i];
        answer += h;
        if (!flag && atoi(h.c_str()) == longest) {
            for (int i = 0; i < additional; i++) answer += to_string(longest);
            flag = true;
        }
    }
    cout << answer << '\n';
 
    return 0;
}