[백준 알고리즘] Node.js 2057. 팩토리얼 분해

1. 문제

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

2057번: 팩토리얼 분해

 

2. 풀이

• 서로 다른 정수로 팩토리얼의 합을 나타낼 수 있는지 알아보는 문제이다. 꼭 연속적인 숫자로 만들 필요가 없다!
• 0! 이 "YES"로 나올 것 같지만 "NO" 란다. 문제가 애매한 느낌이다.

// 받아온 값을 BigInt로 변환. N의 값이 1,000,000,000,000,000,000 까지 이기 때문.
const num = BigInt(require('fs').readFileSync('/dev/stdin').toString().trim());

// 팩토리얼을 구하는 함수
const factorial = (n) => {
  if(n === 0) return 1;
  return n * factorial(n-1);
}


const findAns = (n) => {
  if(n === 0n) return 'NO'; // 0이라면 만들 수 없으므로 바로 리턴.

  const facs = new Array(); // 팩토리얼을 계산한 값을 담아둘 배열.
  let idx = 0; 
  while(BigInt(factorial(idx)) <= n){
    facs[idx] = BigInt(factorial(idx));
    idx++;
  }

  // n 값을 유지시키고 싶어서 sum이라는 변수에 값을 담아둠.
  let sum = n;
  for(let i = facs.length - 1; i >= 0; i--){
    // 만약 sum이 팩토리얼에 담겨있는 수보다 크면 sum에서 빼줌.
    if(sum >= facs[i]) sum -= facs[i];
  }

  // sum이 0이 되면 팩토리얼들로 만들 수 있다는 의미로 "YES", 그 외엔 "NO"
  if(sum === 0n) return 'YES';
  else return 'NO'
}

console.log(findAns(num))

 

3. 정리

• 처음엔 BIgInt 형태로 풀지 않고, 일반적인 정수로 생각하고 풀었다. num의 값을 + 형태로 변환시켰는데 이게 문제였나보다. 그래서 N이 최대값일 때를 vscode로 작성을 해서 비교해봤는데, vscode에선 정상적으로 작동된다................... 음..........
• 아무튼 값의 형태를 주의해서 풀 수 있도록 해야겠다.