백준 - 6463번 팩트 python 문제풀이 [Hellfer]

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

문제

N!은 "N 팩토리얼"로 읽으며, 처음 N개의 양의 정수를 곱한 값이다. 이때, N은 음이 아닌 정수이어야 한다.

예를 들면 다음과 같다.

 N       N! 
 0       1 
 1       1 
 2       2 
 3       6 
 4      24 
 5     120 
10 3628800

N을 입력 받아 0이 아닌 마지막 자리를 구하는 프로그램을 작성하시오.

예를 들어, 5!의 경우에 정답은 2이다. 5! = 120이고, 2는 0이 아닌 마지막 자리이기 때문이다.

🔷 알고리즘 분류 - 다이내믹 프로그래밍

난이도 - 실버 5

🔶문제 풀이 - 재귀함수를 이용한 풀이

def factorial(x):
    # y를 1로 초기화
    y = 1
    # 1부터 x까지 반복
    for i in range(1, x + 1):
        # y에 현재 숫자 i를 곱함
        y *= i
        # y가 10으로 나누어 떨어지는 동안 10으로 나눠 0을 제거
        while y % 10 == 0:
            y //= 10
        # y의 크기를 너무 크게 하지 않기 위해 100000으로 나눈 나머지만 유지
        y %= 100000
    # 최종 y의 0이 아닌 마지막 자리를 반환
    return y % 10

# 무한 루프를 돌며 사용자 입력을 받음
while True:
    try:
        # 사용자로부터 정수를 입력받음
        n = int(input())
        # 입력받은 정수 n에 대해 0이 아닌 마지막 자리를 구함
        result = factorial(n)
        # 형식에 맞게 출력 (n을 오른쪽 정렬하여 5칸 확보하고 " -> ", 결과값 출력)
        print(f'{n:5} -> {result}')
    except EOFError:
        # EOFError가 발생하면 (입력의 끝), 루프를 종료
        break

🔶문제 이해하기

1. 재귀 함수 while 문 안쪽에 y 값을 10이 아닌 10000으로 나눠줘야 정답이 되는 이유
- 계산 중간에 발생하는 매우 큰 수를 관리하기 위해 계산 결과를 일정 크기로 자르는 방법 사용

 

2. 파일 입력은 try와 except 문을 사용해 파일의 끝인 EOFError가 발생하여 루프를 종료