문제
이번 ACM-ICPC 대회에 참가한 모든 사람들은 선물을 하나씩 준비했다.
대회가 끝나고 난 후에 각자 선물을 전달하려고 할 때, 선물을 나누는 경우의 수를 구하는 프로그램을 작성하시오.
모든 사람은 선물을 하나씩 받으며, 자기의 선물을 자기가 받는 경우는 없다.
입력
첫째 줄에 ACM-ICPC 대회에 참가한 학생의 수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다.
예제 입력 1
5
예제 출력 1
나의 풀이
- 통과
- 점화식만 발견한다면 DP로 쉽게 풀 수 있는 문제이다. ai 수열은 a1 = 0, a2 = 1, a3 = 2, a4 = 9, a5 = 44, ... (단, i는 자연수) 순서대로 나열된다. 이 수열을 잘 관찰하면 ai는 ai-1, ai-2의 값이 부분적으로 중복되기에 ai = (i-1)*(ai-1+ai-2)임을 알 수 있다. i번째 값은 i-1번째와 i-2번째 값만 필요로 하므로 길이가 2인 1차원 DP 테이블을 생성한다.
- 단, 이 문제를 Python으로 풀이할 때 주의할 점은 MOD 연산이다. 1 ≤ N ≤ 1,000,000인 조건을 고려할 때 10^12보다 큰 ai가 여러 개 존재할 것이다. 문제에서 경우의 수를 1,000,000,000으로 나눈 나머지를 출력하라고 하였으니 이를 루프가 반복될 때마다 실행해 성능 저하를 예방해야 한다.
import sys
N = int(sys.stdin.readline())
if N <= 2:
print(N-1)
sys.exit()
dp = [0,1]
for i in range(3,N+1):
prev0,prev1 = dp[0],dp[1]
dp[0] = prev1
dp[1] = (i-1)*(prev0+prev1)%1000000000
print(dp[1]) 
SAY CHEESE