백준 / 팩토리얼5 / 1564번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 팩토리얼5 / 1225번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/1564

 

문제 설명

 

---

 

나의 풀이

 

N = int(input())

def factorial(n):
    # 동적 계획법을 위한 테이블 초기화
    dp = [1] * (n + 1)
    
    # 팩토리얼 계산, 뒤의 0을 줄이기 위해 각 단계에서 10의 배수를 줄여 나간다.
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] * i
        while dp[i] % 10 == 0:
            dp[i] //= 10
        dp[i] %= 100000000000000000  # 뒤 0이 아닌 숫자를 추적하기 위해 필요한 자리수만 유지
    
    return dp[n]

number = str(factorial(N))
five = []
d = 0

# 뒤에서부터 0이 아닌 5자리를 찾기
for i in range(len(number) - 1, -1, -1):
    if d == 0 and number[i] == '0':
        continue
    elif d == 0 and number[i] != '0':
        d = 1
        five.append(number[i])
    elif d == 1:
        five.append(number[i])
    if len(five) == 5:
        break

# 결과를 역순으로 출력
print("".join(five[::-1]))

---

※ 알아야 할 것

 

팩토리얼을 동적계획법(DP)을 이용하여 풀면 메모리 사용을 줄일 수 있다.

아마도 실버 1 문제라서 재귀함수로 풀게되면 시간초과가 뜰 것 같다.