[백준 2057번] 팩토리얼 분해 (C++)

문제링크 : https://www.acmicpc.net/problem/2057

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

ll arr[20];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll N;
    cin >> N;

    if(N==0) 
    {
        cout << "NO";
        return 0;
    }

    arr[0]=1;
    for(ll i=1; i<20; i++)
    {
        arr[i] = arr[i-1] * i;
    }

    for(ll i=19; i>=0; i--)
    {
        if(N>=arr[i]) N-=arr[i];
    }

    cout << (N==0 ? "YES" : "NO");
    return 0;
}

 

먼저 가능한 팩토리얼을 모두 계산해준다.

N이 10의 18제곱까지 이기에, 19!까지 계산할 필요가 있다. 

(19! -> 121,645,100,408,832,000 [약 1.2* 10^17])

 

이후에는 그리디하게 접근하여 가장 큰 값 부터 N을 감소시킨다.

만약 N이 무사히 0에 도달한다면 가능한 것이다.

 

예외 처리로 N이 0일 때는 바로 NO를 출력해야 한다.