N = int(input())
DP = [0]*(N+2); DP[2] = 2
for n in range(3,N+1):
DP[n] = DP[n-1]*n*(n-1) + DP[n-2]*n*(n-1)**2
DP[n] %= 10**9+7
print(DP[N])DP로 해결하였다.
까다로운 문제였다. 아이디어를 떠올리기 쉽지 않았다.
아이디어를 설명하면,
1. i번째 줄과 j번째 줄이 같은 칸에서 하나는 파란색, 하나는 빨간색일 때, i번째 줄과 j번째 줄을 "연결되어있다" 라고 정의하자.
2. i번째 줄과 j번째 줄은 두번 연결되어있을 수도 있고, 한번만 연결되어 있을 수 있다.
3. N번째 줄을 추가할 때, N-1번째 줄과 연결되어있다고 가정하자. 그러면 N-1줄과 N줄은 두번 연결된 경우가 있을 수 있고, 한번만 연결되어 있을 수 있다.
4. 두번 연결된 경우, 연결된 두 개의 줄을 독립적으로 취급해줄 수 있다. 그럼 N번째 줄과 N-1번째 줄을 제외한 나머지 경우의 수는 DP[N-2]와 같다. 이때 N번째 줄과 N-1번째 줄이 어느 위치에 들어갈 지 정하는 경우의 수 (N-1)*N, N번째 줄과 N-1번째 줄이 어느 칸에서 연결될 지 정하는 경우의 수 N-1 (나머지 하나는 무조건 N번째 칸이므로). 즉 DP[N-2]*N*(N-1)^2가 된다.
5. 한번 연결된 경우, 경우의 수는 DP[N-1]과 같다. 이때 N번째 줄이 어느 위치에 들어갈 지 정하는 경우의 수 N, 몇번째 줄과 연결할 지 정하는 경우의 수 N-1, 즉 DP[N-1]*N*(N-1)이다.
6. 점화식을 이용해서 bottom-up으로 DP배열을 채우고 결과를 출력한다.
bottom-up DP는 항상 구현은 매우 간단한데 점화식을 찾기가 까다로운 것 같다.
오늘의 교훈) 점화식을 잘 찾자