[다이나믹 프로그래밍 / 파이썬 ] 백준 1947번 : 선물 전달 / 골드 2

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

1947번: 선물 전달

n = int(input())

temp = [0, 1, 2]
if n < 3:
    print(temp[n-1])
    quit()

dp = [0 for _ in range(n+1)]
dp[1] = 0
dp[2] = 1
dp[3] = 2

for i in range(4, n+1):
    dp[i] = ((dp[i-1] + dp[i-2])*(i-1)) % 1000000000

print(dp[n])

각자 가져온 선물을 나눠 갖는데, 본인 것은 가지면 안된다. 이때 경우의 수는?

매우 간단한 질문이지만 규칙을 찾는 것은 상당히 어렵다. 

 

dp로 접근해보자.

a, b, c 세명이 있던 상황에 d가 갑자기 추가된 상황을 떠올려보자.

이때 d가 a의 선물을 선택했다고 해보자.

 

1) 이때 a가 d의 선물을 택한다면?

b, c가 b, c의 선물을 나눠가지면 된다. 즉 dp(n-2) 가지가 가능하다.

 

2) a가 d의 선물을 택하지 않았다면?

a, b, c가 b, c, d의 선물을 나눠가지면 되고, 이때 d의 선물을 어차피 a는 택하지 않을 거니까 그냥 a의 선물이라고 여기면 dp(n-1) 가지가 가능하다.

 

이 둘을 더하면 dp(n-1) + dp(n-2)가 되고, d가 처음에 a, b, c의 선물 중 하나를 택할 수 있으므로

점화식은 다음과 같아진다.

dp(n) = ( dp(n-1) + dp(n-2) ) * (n-1)