팩토리얼 분해 (백준 2057)

안녕하세요. 오늘은 분해를 해볼 거예요.

문제

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

아이디어

able(x,mx)를 x를 mx이하의 수 0개 이상을 써서 팩토리얼 분해할 수 있는지 라고 정의합시다. mx부터 하나씩 내려가면서 그 팩토리얼 값이 x이하이면 빼주고 able해주면 됩니다. 만약 그게 아니라면 그냥 mx만 바꿔서 able해주면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll fact(ll x)
{
    ll mul = 1;
    while (x)
        mul *= x--;
    return mul;
}
bool able(ll x, ll mx)
{
    if (mx == -1 && x != 0) return false;
    if (x == 0) return true;

    if (fact(mx) <= x) return able(x - fact(mx), mx - 1);
    return able(x, mx - 1);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll x;
    cin >> x;
    if (x != 0 && able(x, 20)) cout << "YES";
    else cout << "NO";
}

감사합니다.