문제
음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 방식으로 나타낼 수 없다.
입력
첫째 줄에 정수 N이 주어진다.
출력
입력으로 주어진 수를 서로 다른 정수 M개의 팩토리얼의 합으로 나타낼 수 있으면 YES, 없으면 NO를 출력한다.
예제 입력
1
5
예제 출력
1
NO
풀이과정
처음엔 브루트포스 알고리즘을 사용하여 N!부터 0!, 1!… 하나씩 빼면서 조건이 충족될 때 까지 반복문을 돌리면 된다고 생각했으나 이에 반례가 존재해서 다시 코드를 짜보았다. 천천히 다시 생각을 해보니 1!부터 n! 까지의 합이 n+1!보다 작다는 점을 알았고, N이 주어지면 N보다 작거나 같은 최대의 x!을 빼고 뺀 그 수를 위의 조건에 다시 적용하는 반복문을 짰다.