모든 챌린지
어려움 0명 해결 정답률 0%

자릿수 팩토리얼 체인

자릿수 팩토리얼 체인의 서로 다른 항이 정확히 주어진 개수인 시작 수를 셉니다.

배우게 될 내용

  • 값이 반복될 때까지 체인을 따라갈 수 있다
  • 고리 안과 고리 앞의 체인 길이를 구할 수 있다
  • 저장해 둔 길이를 재사용할 수 있다

문제

원문 보기 (영어)

수를 각 자리 숫자의 팩토리얼 합으로 바꿔 봅시다. 145는 1! + 4! + 5! = 145로 다시 자기 자신이 되고, 69는 6! + 9! = 363600이 됩니다. 이를 반복하면 반드시 어떤 고리에 빠지게 됩니다. 시작 수의 체인은 처음으로 반복이 나오기 전까지의 항들입니다. 69, 363600, 1454, 169, 363601 다음에 다시 1454가 나오므로 69의 체인에는 서로 다른 항이 5개 있습니다. 1부터 limit까지의 시작 수 중에서 체인의 서로 다른 항이 정확히 length개인 수를 세세요.

digit_factorial_chains(limit, length) 함수를 구현하세요.

많은 체인이 같은 수들을 거쳐 갑니다. 각 수의 체인 길이를 알게 되면 저장해 두었다가 다시 사용하세요.

입력

limit: 가장 큰 시작 수입니다.

length: 원하는 서로 다른 항의 개수이며 시작 수도 포함합니다.

출력

1 ≤ n ≤ limit인 시작 수 n 중에서 체인의 서로 다른 항이 정확히 length개인 수의 개수를 반환합니다.

제약 조건

1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70

예시

예시 1
입력:
limit = 2
length = 1

예상 출력:
expected = 2
입력:
long long limit = 2;
long long length = 1;

예상 출력:
long long expected = 2;
입력:
long limit = 2;
long length = 1;

예상 출력:
long expected = 2;

설명

1! = 1, 2! = 2이므로 1과 2는 각각 자기 자신으로 바뀌어 체인의 항이 1개입니다. 답은 2입니다.

예시 2
입력:
limit = 10
length = 2

예상 출력:
expected = 1
입력:
long long limit = 10;
long long length = 2;

예상 출력:
long long expected = 1;
입력:
long limit = 10;
long length = 2;

예상 출력:
long expected = 1;

설명

3은 6, 720, 5043, ...으로 이어져 깁니다. 10은 1! + 0! = 2가 되고 그다음도 2이므로 항이 두 개입니다. 정확히 2개인 수는 10뿐이므로 답은 1입니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

0!부터 9!까지 미리 한 번 계산해 두세요.

힌트 2

현재 체인에서 각 값이 몇 번째 단계인지 기록하세요. 반복이 나오면 고리가 어디서 시작하는지 알 수 있습니다.

힌트 3

고리 안의 값은 모두 고리의 길이를 가지며, 고리 앞의 각 값은 다음 값보다 1이 더 깁니다.

예상 복잡도

시간 O(limit × log limit) (메모이제이션 사용 시), 추가 공간 O(limit)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.