영훈이의 색칠공부( BOJ 14578 )

문제 : https://www.acmicpc.net/problem/14578

14578번: 영훈이의 색칠공부

 

문제 파악하기

N*N 격자판에 빨간색과 파란색을 색칠하는 경우의 수를 구하는 문제입니다. 당연히 아무 칸에 색칠할 수 있는 건 아니고, 모든 행과 열에 빨간색과 파란색을 하나씩 색칠해야 합니다. 결국 N개의 빨간색과 파란색을 행과 열이 중복되지 않게 배치할 수 있는 방법의 수를 구하는 문제입니다. 2차원 배열을 하나씩 채워 나가기에는 10⁵라는 숫자가 너무도 크기에 다른 방법을 생각해보아야 합니다. 그럼 어떤 방법이 있을까요?

 

우선은 문제를 분석해봅시다. 만약 3*3격자판에서 빨간색이 다음과 같이 색칠되었다고 가정해봅시다.

이 경우, 빨간색이 색칠된 위치를 행 순서대로 열을 기록하면 { 1, 2, 3 } 이라는 순열이 나오게 됩니다. 여기서 파란색을 색칠하기 위해서는 어떤 조건을 만족해야 할까요? 바로, 빨간색이 색칠된 위치에 절대 색칠하지 않는다는 조건입니다. 그렇다면 파란색을 색칠한 다음, 파란색이 색칠된 위치를 행 순서대로 열을 { a, b, c }와 같이 기록했다고 가정해봅시다. 이 때, 조건을 만족하기 위해서는 다음 조건을 만족해야 합니다.

a != 1 / b != 2 / c != 3

위의 조건을 만족하는 순열의 개수를 구하는 것은 간단합니다. 바로 완전 순열을 사용하면 됩니다.

문제 해결하기

완전순열이란 모든 숫자가 자기 순번에 위치하지 않는 순열을 의미합니다. { 2, 4, 1, 3 }은 완전수열이며, { 1, 4, 2, 3 }은 완전수열이 아닙니다. i개의 숫자로 만들 수 있는 완전순열의 수는 다음 점화식을 통해 쉽게 구할 수 있습니다.

DP[i] = (i-1)*DP[i-1] + (i-1)*DP[i-2]

이렇게 완전순열의 개수를 구하면 구한 개수를 활용하면 문제를 해결할 수 있습니다. 완전순열은 결국 각각의 숫자가 있어서는 안 되는 위치가 1개씩 있으며, 모든 숫자가 해당 위치에 없는 순열을 의미합니다. 이는 빨간색이 색칠된 위치에 파란색을 색칠할 수 없다는 의미와 동일하며, 따라서 우리는 빨간색을 색칠할 수 있는 모든 경우마다 나올 수 있는 완전순열의 개수를 구하면 원하는 해답을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#define NMAX 100010
#define MOD 1000000007
 
int N;
long long int dp[NMAX];
 
long long int fac(int k) {
    long long int ret=1;
    for(int i=1;i<=k;i++) ret = (ret*i)%MOD;
 
    return ret;
}
 
int main() {
    scanf("%d", &N);
 
    dp[0] = 1;
    for(int i=2;i<=N;i++) dp[i] = (i-1)*((dp[i-1]+dp[i-2])%MOD)%MOD;
    printf("%lld", (dp[N]*fac(N))%MOD);
}

후기

완전순열이 숨어있는 다이나믹 프로그래밍 문제입니다. 점화식을 떠올리는게 힘든 전형적인 다이나믹 프로그래밍 문제라고 생각합니다.