[Python]백준_2057 : 팩토리얼 분해

2022년 12월 16일에 작성됨

 

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

2057번: 팩토리얼 분해

 

 

문제 분석

큰 팩토리얼부터 살펴보면서 그 값이 n보다 작으면 변수 sum에 더해주고 크면 넘어가는 식으로 반복해서 누적합 sum이 n과 같아지는지 비교해본다.

 

 

소스 코드 (⭕)

n = int(input())

# 1! ~ 20! 까지 값을 구함
fact = [1, 1]
for i in range(2, 21):
    fact.append(fact[i-1]*i)

sum = 0

for i in range(20, -1, -1):
    # 20!부터 살펴보면서 팩토리얼 누적 합을 구함
    if sum+fact[i] < n:
        sum += fact[i]
    elif sum+fact[i] == n:      # 누적 합이 정수 n과 같은 경우
        print("YES")
        exit(0)

print("NO")

 

코드 분석

1. 정수 n의 범위의 최댓값은 21!을 넘지 않으므로 20! 까지만 구하여 fact 안에 넣어준다.

2. 20!부터 n보다 작은 범위인지 판단해준다.

3. sum+k!이 n보다 작으면 sum에 더해주고, 크면 (k-1)!을 보는 식으로 반복을 진행해준다.

4. 그러다 sum이 정수 n과 같아지는 경우 YES를 출력하고, 반복문을 끝까지 돌렸는데도 n와 같아지는 경우가 없으면 NO를 출력한다.

 

 

 

end

나는 큰 팩토리얼부터 비교해봤는데 작은 팩토리얼부터 하는 분들도 있었다.