BOJ 5692 - 팩토리얼 진법

문제

팩토리얼 진법으로 표현된 수를 10진법으로 변환하라. 팩토리얼 진법에서 i번째 자릿수(오른쪽부터)는 i!의 가중치를 가진다.

입력

여러 팩토리얼 진법 수가 주어지며, 0이면 종료한다.

출력

각 수를 10진법으로 출력한다.

예제

입력	출력
`719` `0`	`53`

풀이

각 자릿수에 해당하는 팩토리얼 가중치를 곱하여 합산한다.

팩토리얼 값 배열을 미리 계산한다 (1!, 2!, 3!, ...)
입력 수의 각 자릿수(오른쪽부터)에 대응하는 팩토리얼을 곱한다
곱한 값의 합이 10진수 결과이다

핵심 아이디어: 팩토리얼 진법은 i번째 자릿수의 값이 d * i!이므로, 위치별 가중치 합산으로 변환한다.

코드

#include <iostream>
 
using namespace std;
 
int N;
int arr[6];
 
bool init()
{
 
  cin >> N;
  return N;
}
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 0; i < 5; i++)
  {
    if (i == 0)
      arr[i] = 1;
    else
      arr[i] = arr[i - 1] * (i + 1);
  }
  while (init())
  {
    int temp = N;
    int j = 0;
    int sum = 0;
    while ((temp % 10) || (temp / 10))
    {
      sum += (temp % 10) * arr[j++];
      temp /= 10;
    }
    cout << sum << "\n";
  }
 
  return 0;
}

복잡도

시간: O(자릿수)
공간: O(1)

문제