[백준 / BOJ] C++ 29158 큰 수 만들기 게임

29158번: 큰 수 만들기 게임

 

문제

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

29158번: 큰 수 만들기 게임

 

 

풀이

큰 수를 만드는 테크닉은 16496 - 큰 수 만들기 문제와 동일하다.

각각의 수를 문자열로 a = "1", b = "2"인 경우 ab = "12" ba = "21"로 더 큰 수를 만들 수 있는 것은 ba다. 이 정렬 조건으로 수를 정렬한 다음 차례대로 나열하면 된다.

 

먼저 동작 1과 동작 2가 있는데, 동작 1은 2 이상의 K로 2 초과의 D를 나눌 수 있을 경우 K와 D/K로 나누는 동작이다. 나눈 결과가 많을수록 수는 커지기 때문에 입력받은 정수 N을 소인수분해한다. 그리고 위 테크닉을 사용해 큰 수를 만든다. 동작 2는 동작 1의 반대 과정이므로 사용하지 않는다.

그리고 M은 N 미만의 수 중 가장 큰 수를 만들 수 있어야 한다. 따라서 M은 N-1을 2로 나누어가다가 4 미만이 됐을 때, 그동안 나눈 2와 남은 2 또는 3으로 이루어진 수가 된다. 마찬가지로 위 테크닉으로 큰 수를 만든다.

 

여기서 N의 입력 범위가 10^12까지인데, 당장 10^12도 소인수분해하면 2^12*5^12이다. 이를 큰 수로 만들면 555555555555222222222222인데, 24자리 수이므로 long long 범위를 초과한다. 즉, 큰 수 연산이 필요하다. 먼저 각각의 큰 수 문자열을 a와 b라고 했을 때, 길이가 작은 문자열의 앞에 0을 추가해 길이를 같게 만들어준다. 그리고 a(또는 b)의 길이 + 1 크기의 배열을 만들어준다(마지막 carry가 있을 수 있기 때문). 가장 뒷자리부터 한 자리씩 연산을 한다. 만약 연산 결과 마지막에 carry가 발생하지 않는다면(즉, ans배열의 0번 index의 값이 0이면) 1번 index의 값부터 모두 출력하고, 아니라면 모두 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long

bool cmp(string a, string b) {
  string ab = a + b;
  string ba = b + a;
  return ab > ba;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n, t;
  cin >> n;
  t = n - 1;
  vector<string> v;
  for (ll i = 2; i * i <= n; i++)
    while (n % i == 0) {
      v.push_back(to_string(i));
      n /= i;
    }
  if (n > 1)
    v.push_back(to_string(n));
  sort(v.begin(), v.end(), cmp);
  string a = "", b = "";
  for (string i : v)
    a += i;
  v.clear();
  while (t > 3) {
    v.push_back("2");
    t /= 2;
  }
  v.push_back(to_string(t));
  sort(v.begin(), v.end(), cmp);
  for (string i : v)
    b += i;
  if (a.size() > b.size()) {
    string tmp = "";
    while (tmp.size() < a.size() - b.size())
      tmp += '0';
    b = tmp + b;
  } else {
    string tmp = "";
    while (tmp.size() < b.size() - a.size())
      tmp += '0';
    a = tmp + a;
  }
  vector<int> ans(a.size() + 1, 0);
  for (int i = a.size() - 1; i >= 0; i--) {
    int x = a[i] - '0';
    int y = b[i] - '0';
    if (x + y + ans[i + 1] < 10) {
      ans[i + 1] = x + y + ans[i + 1];
    } else {
      ans[i] = 1;
      ans[i + 1] = x + y + ans[i + 1] - 10;
    }
  }
  if (ans[0])
    for (int i : ans)
      cout << i;
  else
    for (int i = 1; i < ans.size(); i++)
      cout << ans[i];
  return 0;
}