알고리즘/BOJ 문제풀이

[Greedy] BOJ 1422_숫자의 신

4Legs 2020. 10. 15. 23:40

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

 

1422번: 숫자의 신

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보��

www.acmicpc.net

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

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

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

 

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

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

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

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

 

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

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

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

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

 

[코드]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
typedef pair<intint> 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;
}
cs

 

'알고리즘 > BOJ 문제풀이' 카테고리의 다른 글

[Dijkstra]BOJ 16118_달빛 여우  (0) 2020.10.23
[Dijkstra]BOJ 9370_미확인 도착지  (0) 2020.10.23
[DP] BOJ 1256_사전  (0) 2020.10.15
[Segtree]BOJ 2243_사탕 상자  (0) 2020.10.12
[BFS]BOJ 16236_아기 상어  (0) 2020.10.11