(백준 / BOJ) C++ 4839 Exhaustion

4839: 배기 방식

질문

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

설명하다

소수의 곱셈을 사용하는 문제. 다만, 숫자의 범위가 int의 범위 안에 있기 때문에 29를 곱하면 23까지 범위 밖의 곱만 요구하면 된다.

그래서 누적상품(?) 시리즈를 만든다.

가장 큰 누적 곱을 비교하여 N이 누적 곱보다 크거나 같으면 N을 누적 곱의 몫으로 나누고 소수점 곱을 누적 곱에 다음을 준수하는 문자열 형식으로 배열에 추가합니다.

출력 형식. 그런 다음 누적 곱으로 나눈 나머지로 N을 업데이트합니다.

누적 곱 배열을 모두 확인하고 나머지 N이 0보다 크면(1인 경우) N을 출력한 다음 배열에 저장된 값을 출력합니다.

(출력 형식이 까다롭습니다.

)

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  while (1) {
    int n;
    cin >> n;
    if (!
n)
      break;
    int origin = n;
    vector<int> prime{2, 3, 5, 7, 11, 13, 17, 19, 23}, v(9, 0);
    for (int i = 1; i < 9; i++)
      v(i) = v(i - 1) + prime(i);
    vector<string> ans;
    for (int i = v.size() - 1; i >= 0; i--) {
      if (v(i) <= n) {
        int cnt = n / v(i);
        n %= v(i);
        string tmp = to_string(cnt);
        for (int j = 0; j <= i; j++)
          tmp += "*" + to_string(prime(j));
        ans.push_back(tmp);
      }
    }
    cout << origin << " = ";
    if (n > 0)
      cout << n;
    for (int i = ans.size() - 1; i >= 0; i--) {
      if (i !
= ans.size() - 1 || n > 0)
        cout << " + ";
      cout << ans(i);
    }
    cout << '\n';
  }
  return 0;
}