[백준 / BOJ] C++ 1422 숫자의 신

1422번: 숫자의 신

 

문제

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

1422번: 숫자의 신

 

 

풀이

K개의 수를 N번 사용해 가장 큰 수를 만드는 문제다. 단, 모든 수는 한 번은 이용해야 한다.

 

1. K개의 수 정렬

연결했을 때 가장 큰 수를 만들기 위해서 말 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경우엔 110이 더 크기 때문에 위치가 바뀌지 않는다. 이 기준만으로 정렬한 후 출력하면 K개의 수를 모두 사용할 수는 있지만 N번 사용할 수는 없다.

 

아래 16496번 큰 수 만들기 문제와 정렬 기준이 같다. 

https://khyunx.tistory.com/79

[백준 / BOJ] C++ 16496 큰 수 만들기

 

 

2. 남은 횟수만큼 출력할 수 정렬

그러면 N개의 수를 사용해 가장 큰 수를 만들려면 가장 적절한 수 하나를 N-K번 사용하는 것이다. 여기서 가장 적절한 수는 두 가지 기준을 세웠다. 1. 수의 길이가 가장 길 것 2. 길이가 같다면 연결했을 때 큰 수 로 정했다. 왜냐하면 수의 길이가 긴 수를 반복해서 쓸수록 더 큰 수가 만들어질 것이고, 길이가 같다면 더 큰 수가 적합하기 때문이다. 이 기준에 따라 정렬하면 배열의 가장 앞에 해당 수가 온다.

 

따라서 1번 과정에 따라 정렬된 배열에서 가장 큰 수가 되도록 원소 하나씩 출력하며 2번 과정에 의해 나온 가장 적절한 수가 출력될 차례에 이 수를 N-K번 출력하도록 코드를 작성했다. 그리고 만약 같은 수가 원래 여러 개 출력될 예정이었을 경우에 대비해 flag를 사용해 여러 번 반복하지 않도록 제한을 뒀다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

// 1번 과정 정렬 기준
bool compare(string a, string b) {
  string ab = a + b;
  string ba = b + a;
  return ab > ba;
}

// 2번 과정 정렬 기준
bool cmp(string a, string b) {
  if (a.size() == b.size()) {
    string ab = a + b;
    string ba = b + a;
    return ab > ba;
  }
  return a.size() > b.size();
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int k, n, flag = 0;
  cin >> k >> n;
  vector<string> v(k), tmp;
  for (int i = 0; i < k; i++)
    cin >> v[i];
  tmp = v;
  sort(tmp.begin(), tmp.end(), compare); // 1번 과정 정렬
  sort(v.begin(), v.end(), cmp); // 2번 과정 정렬
  for (int i = 0; i < k; i++) {
    if (tmp[i] == v[0] && !flag) {
      for (int j = 0; j < n - k + 1; j++)
        cout << tmp[i];
      flag = 1;
    } else
      cout << tmp[i];
  }
  return 0;
}