[실버 5] 백준 31738 - 매우 어려운 문제 (파이썬)

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

풀이

이 문제는 시간에 매우 민감한 문제이다.

# 백준 31738 - 매우 어려운 문제
# 분류 : 수학

import math
N, M = map(int, input().split())
if N >= M :
    print(0)
else :
    print(math.factorial(N) % M)

대충 이렇게 math 패키지로 팩토리얼을 계산한 경우 시간 초과가 일어나게 된다. 아마 계속해서 수를 증가시키면서 곱하기 때문에 시간 초과가 일어나는것으로 보인다.

먼저 N이 M보다 큰 경우에는 어떤 수로 나누어도 0이 나올 수 밖에 없다.

수학적으로 N ≥ M인 경우 M은 N!의 약수가 되므로 N! mod M = 0이 된다

예를들어서 5! = 120, M = 5인 경우 120 mod 5 = 0 이다.

else :
    d = 1
    for i in range(1, N + 1) :
        d *= i
        d %= M
    print(d)

N ! mod M 을 계산한다. 파이썬은 큰 정수도 다룰 수 있지만 mod를 중간중간 해주는 것이 효율적이다.

d %= M 을 반복적으로 해줘서 값이 너무 커지지 않도록 한다.

코드

# 백준 31738 - 매우 어려운 문제
# 분류 : 수학
N, M = map(int, input().split())

if N >= M :
    print(0)
else :
    d = 1
    for i in range(1, N + 1) :
        d *= i
        d %= M
        
    print(d)