백준 2057 < 팩토리얼 분해 > JavaScript

📍문제 링크

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

2057번: 팩토리얼 분해

 

📍알고리즘 분류

- 수학

- 그리디

- 브루트포스

 

📍문제 풀이

주어진 수 N이 서로 다른 팩토리얼의 합으로 나타낼 수 있는지 묻는 문제

그리디 알고리즘의 전형적인 문제같다

 

N의 범위가 매우 크므로 (0 ≤ N ≤ 1,000,000,000,000,000,000)

BigInt 로 감싸줘야 한다!

 

0! = 1

1! = 1 임을 유의하자

 

📍의사 코드

1. N보다 작은 X! 의 최댓값을 구할 때까지 배열에 저장

- [ 0!, 1!, ... X! ] 이 기록됨

 

2. 배열의 X! 부터 0! 까지 역으로 순회하며 N에서 차감해보는데, 차가 0 이상일 때만 수행을 반복

- 반복 중 0이 되면 YES!

- 반복문이 종료되면 0이 아니므로 NO!

 

📍코드 (JavaScript)

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = BigInt(input);
const solution = () => {
  if (N === 0n) return "NO";
  if (N <= 2n) return "YES";

  memo = [1];
  for (let i = 1; i <= N; i++) {
    memo[i] = memo[i - 1] * i;
    if (memo[i] > N) break;
  }

  let num = N;
  for (let i = memo.length - 2; i >= 0; i--) {
    if (num >= BigInt(memo[i])) num -= BigInt(memo[i]);
    if (num === 0n) {
      return "YES";
    }
  }
  return "NO";
};

console.log(solution());