백준 10978, 기숙사 재배정

개요

문제 링크
골드 2, DP
p[i] != i이도록 permutation 구성하기

---

접근

1. 수능 경우의 수에서도 종종 보이는 문제, 수능에서는 수형도를 그리라고 지시한다. 노가다를 하라는 의미.

2. 하지만 DP를 이용하면 논리적으로 문제를 해결해줄 수 있다. 아래 예시를 보자.

   // n = 5
   ABCDE
   B????

   ABCDE의 첫 자리에는 A가 오면 안되고, BCDE가 올 수 있는데, 첫 자리 수를 제외한 나머지 수의 구성은 (같은,다른)이 (3,1)로 동일하므로 B가 앞자리에 오는 경우 × 4를 해주면 된다. 즉 f(5) = (3,1) × 4

3. 그럼 위 예시의 정답을 구해보자.

   ABCDE
   BA??? -> (3,0) = f(3)
   
   (2,1) (BC??? BD??? BE???)
   BCA?? -> f(2)
   BCD?? -> 1
   BCE?? -> 1
   
   (3,1) = (3,0) + 3*(2,1) = f(3)+3*(f(2)+1+1) = 2+3*3 = 11
   f(5) = 4*(3,1) = 4*11 = 44

   B의 다음에는 A와 CDE가 올 수 있는데, A가 오는 경우 나머지의 구성은 f(3)과 같아진다. CDE가 오는 경우는 (2,1)로 구성이 동일하다. 그래서 3을 곱해주면 된다. 예시를 하나 더 보자.

   // n = 6
   ABCDEF
   BA???? -> (4,0) = f(4)
   
   (3,1) (BC, BD, BE, BF)
   BC???? // 구할 필요가 없다. 이미 (3,1)은 구해둠.
   
   (4,1) = (4,0) + 4*(3,1) = 9+44
   f(6) = 5*(4,1) = 5*53 = 265

   아하. (4,1)의 경우에서 필요한 것은 (4,0), (3,1) 인데 (4,0)은 f(4)이므로 이미 구했고, (3,1)은 f(5)/4로 이미 구해뒀다. 따라서 잘 정리하면 아래 식이 성립한다.

   f(n) = (n-1) * (f(n-2) + (n-2)*f(n-1)/(n-2))
       = (n-1) * (f(n-2) + f(n-1))

---

Pseudo code

dp[1] = 0, dp[2] = 1
for (i = 3~20)
    dp[i] = (i-1) * (dp[i-1]+dp[i-2])

---

Source code

#include <iostream>
using namespace std;

using ld = long long;
ld dp[21];
void test() {
    int n;
    cin >> n;
    cout << dp[n] << "\n";
}

int main() {
    dp[1] = 0, dp[2] = 1;
    for (ld i=3; i<=20; i++)
        dp[i] = (i-1)*(dp[i-1]+dp[i-2]);
    int t;
    cin >> t;
    while(t--) test();
}