Python으로 숫자가 서로 다른 팩토리얼 수의 합으로 표현 가능한지 확인하는 방법

양수 n이 주어졌을 때, 이 숫자가 서로 다른(중복되지 않는) 양의 팩토리얼 수들의 합으로 표현될 수 있는지 확인하는 문제를 살펴보겠습니다.

예를 들어 입력값이 n = 144라면, 4! + 5! = 24 + 120 = 144가 성립하므로 결과는 True가 됩니다.

문제 해결 접근 방식

이 문제는 그리디(Greedy) 알고리즘을 활용하여 해결할 수 있습니다. 핵심 아이디어는 n보다 작거나 같은 모든 팩토리얼 값을 먼저 구한 뒤, 큰 값부터 차례대로 확인하며 n에서 빼주는 것입니다. 마지막에 n이 0이 된다면 해당 숫자는 팩토리얼 수들의 합으로 표현 가능하다는 의미입니다.

알고리즘 단계

• fact := 1 로 초기화합니다.
• res := 새로운 리스트를 생성합니다.
• x := 2 로 초기화합니다.
• fact <= n 인 동안 반복합니다:
  • res 리스트의 끝에 fact를 추가합니다.
  • fact := fact * x 로 갱신합니다.
  • x := x + 1 로 증가시킵니다.
• res 리스트의 마지막 인덱스부터 0까지 역순으로 반복합니다:
  • 만약 n >= res[i] 라면, n := n - res[i] 를 수행합니다.
• 최종적으로 n이 0과 같으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

Python 구현 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

class Solution:
   def solve(self, n):
      fact = 1
      res = []
      x = 2
      while fact <= n:
         res.append(fact)
         fact = fact * x
         x += 1
      for i in range(len(res)-1,-1,-1):
         if n>=res[i]:
            n-=res[i]
      return n==0
ob = Solution()
print(ob.solve(144))

입력

144

출력

True

동작 원리 설명

위 코드가 실행되면 먼저 1!, 2!, 3!, 4!, 5!처럼 n 이하의 모든 팩토리얼 값이 리스트에 저장됩니다. 이후 리스트를 역순으로 순회하면서 현재 남은 n보다 작거나 같은 팩토리얼 값을 빼줍니다. 144의 경우 5!(120)를 먼저 빼면 24가 남고, 이어서 4!(24)를 빼면 정확히 0이 되므로 True가 반환됩니다.

이 그리디 접근법이 항상 올바른 결과를 보장하는 이유는, 각 팩토리얼 수가 이전 팩토리얼 수들의 합보다 크다는 성질 때문입니다. 따라서 큰 팩토리얼부터 선택하는 것이 최적의 선택이 됩니다.