[백준] [DP] 1947. 선물 전달

1947. 선물 전달

1947번: 선물 전달

 

풀이

• n번째 사람이 새로 들어왔다고 쳤을때 A(n)
  • 내가 n번째 사람과 서로 교환한 경우
    • 이미 존재하던 n-1명 그룹 중에서 나를 제외한 n-2명의 사람들끼리 교환
    • n번째 사람이 (반드시 내가 아니라) n-1명 중 한명과 교환하는 것이므로 * (n-1)
      • → A(n-2) * (n-1)
  • n번째 사람 선물을 내가 받아놓고 나는 안 준 경우
    • 내가 받은걸 숨기고 그대로 n-1명끼리 선물 교환 (나는 2개를 받게되지만 하나를 그다음에 n번째사람한테 준다고 치는 것)
    • 여기도 n번째 사람이 (반드시 내가 아니라) n-1명 중 한명과 교환하는 것이므로 * (n-1)
      • → A(n-1) * (n-1)
• → 결과적으로 A(n)= A(n-2) * (n-1) + A(n-1) * (n-1) = (n-1) * (A(n-2) + A(n-1))

 

n = int(input())

if n == 1:  # n=1 이면 dp[1]꺼지 만들어지는데 do[2]를 넣어서 에러
    print(0)
    exit()

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

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

print(dp[n])