[백준 / BOJ] C++ 4839 소진법

4839번: 소진법

 

문제

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

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;
}