[백준/파이썬] 2057번 팩토리얼 분해 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2057번 팩토리얼 분해
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

정수 N을 서로 다른 팩토리얼 값들의 합으로 표현할 수 있는지 판정하는 문제입니다.

코드

n = int(input())

m = [1]

i = 1
while True:
    if m[-1]*i > n: break
    m.append(m[-1]*i)
    i += 1

f = False
def dfs(case):
    if sum(map(lambda i:m[i], case)) == n:
        global f
        f = True
        return
    for i in range(case[-1]+1, len(m)):
        if f:return
        dfs(case + [i])

i = 0
while i < len(m) and not f:
    dfs([i])
    i += 1

print('YES' if f else 'NO')

설명

N 이하의 팩토리얼 수들을 만든 뒤 중복 없이 고르는 조합을 DFS로 탐색해 합이 N이 되는 경우가 있으면 YES를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---