[백준] 재귀 - 10872번 (Python)

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

10872번: 팩토리얼

---

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.

출력

첫째 줄에 N!을 출력한다.

코드 정답

import sys
input = sys.stdin.readline

n = int(input())
num = 1
if (0 < n < 13):
    for i in range(1, n+1):
        num *= i
print(num)

import sys
input = sys.stdin.readline

def factorial(n):
    num = 1
    if (0 < n < 13):
        num = n * factorial(n-1)
    return num

n = int(input())
print(factorial(n))

풀이

두 가지 형식의 풀이방법을 준비해보았다. 1~2행은 같은 것이니 한 번만 설명을 하고 넘어가도록 하겠다.

 

for문 활용

1~2행 : 일반적으로 input 을 사용하게 된다면 시간 초과가 나올 수 있다. 그렇기 때문에 input 과 같으면서도 빠른 sys.stdin.readline 을 사용하기 위해 import sys 란 헤더를 선언해주었고 input 에 sys.stdin.readline 을 대입하여 input 을 sys.stdin.readline 처럼 사용 할 수 있게끔 된다.

import sys
input = sys.stdin.readline

4~9행 : 변수 n 을 선언해주고 값을 입력받아 정수형으로 변환 후 n 에 대입시킨다. 이후 num 이란 변수에 1이란 값을 넣어 선언해준다.

만약 n 이 0 보다 크거나 13 보다 작을 시 for 문이 실행되는데, 1부터 n+1의 전 값이 될 때까지 i 에는 1부터 값을 순차적으로 넣어주며 8행을 실행시킨다. num = num * i 와 같은 문장으로 num 에 i 를 계속해서 곱해주어 마지막에는 1부터 n까지의 값을 전부 곱한 상태의 값이 출력이 된다.

n = int(input())
num = 1
if (0 < n < 13):
    for i in range(1, n+1):
        num *= i
print(num)

 

재귀 함수 활용

4~8행 : def 를 이용하여 factorial 이란 함수를 만들어주었고 받아온 값을 n 이라고 선언을 해준다. num 이란 변수를 함수 내에서 선언을 하여 1이란 값을 대입해주었고 만약 n 이 0보다 크고 13보다 작으면 num = n * factorial(n-1) 이란 문장이 실행이 된다.

여기서 중요한 점은 factorial(n-1) 에 의하여 재귀 함수가 실행이 된다. n 의 값에서 1을 빼낸 값을 다시 함수로 보내버리게 되면 다시 문장이 시작된다. n 에 만약 3이란 값이 입력이 되어있다면 3, 2, 1, 0 까지 줄어들게 되어 return num 이란 문장에 다다를 때까지 반복이 된다. 여기서 return 을 만났다고 print() 로 가는게 아닌, 재귀가 시작되기 바로 전의 상황에 값을 넘겨주게 된다.

이후 처음 재귀가 실행된 장소로 돌아와 if 문을 나가게 된다면 끝에 저장된 값을 리턴시켜준다.

def factorial(n):
    num = 1
    if (0 < n < 13):
        num = n * factorial(n-1)
        # n = 3 이라고 가정을 하고서..
        # num = 3 * factorial(2)
        # num = 2 * factorial(1)
        # num = 1 * factorial(0)
        ############## 리턴으로 1을 받음 #############
        # num = 1 * 1 -> num = 2 * 1 -> num = 3 * 2 가 순차적으로 실행 됨
    return num

10~11행 : 변수 n 에 입력값을 받고 factorial() 이란 이름의 함수에 n 의 값을 보낸다. 함수에서 코드 과정이 거쳐지고 return 되어 돌아온 값을 출력한다.

n = int(input())
print(factorial(n))