JOISC18 Tents

D문제

oj.uz/problem/view/JOI18_tents

문제 보기 - Tents (JOI18_tents) :: oj.uz

N*M의 격자에 텐트를 배치하는데, 각 텐트별 동, 서, 남, 북의 4가지 방향이 있다. 어떤 두 텐트가 같은 행이나 열에 있다면 이 두 텐트는 서로 마주보고 있는 방향이어야 한다. 이 조건들을 모두 만족시킬 때 전체 텐트의 배치로 가능한 경우의 수를 구하자.

$N, M<=3000$

 

풀이

Observation 1 : 한 행이나 열에 위치할 수 있는 텐트는 최대 2개이다.

만약 한 행이나 열에 텐트가 3개 이상 배치된다면, 각 텐트를 서로 마주보게 할 수 없다. 따라서 어떠한 행이나 열에 위치할 수 있는 텐트는 0, 1, 2개이다.

 

DP를 통해 해결하자.

1. 첫번째 행에 2개의 텐트가 있다.

텐트의 방향은 고정이고, 위치를 정해준다. 그 후, 해당하는 두 텐트가 위치한 두 열은 다른 텐트들이 있을 수 없기 때문에 제거해준다.

2. 첫번째 행에 1개의 텐트가 있으며, 1개의 텐트가 있는 열에 다른 텐트가 하나 있다.

1과 같은 논리로 해당 두 텐트의 위치를 결정해준 후, 다른 텐트들이 위치할 수 없는 두 행을 제거해준다.

3. 첫번째 행에 1개의 텐트가 있으며, 1개의 텐트가 있는 열에 다른 텐트가 없다.

텐트의 위치와 방향을 모두 결정하고, 그 행과 열을 제거한다.

4. 첫번째 행에 아무 텐트가 없다.

그 행을 제거한다.

 

시간 복잡도 : $O(NM)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3000;
const ll MOD = 1e9+7;

int N, M;
ll dp[MAXN+10][MAXN+10];

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=0; i<=N; i++) dp[i][0]=1;
	for(int j=0; j<=M; j++) dp[0][j]=1;
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=M; j++)
		{
			if(j>=2) dp[i][j]+=(ll)j*(j-1)/2*dp[i-1][j-2]%MOD;
			dp[i][j]+=(ll)4*j*dp[i-1][j-1]%MOD;
			if(i>=2) dp[i][j]+=(ll)j*(i-1)*dp[i-2][j-1]%MOD;
			dp[i][j]+=dp[i-1][j];
			dp[i][j]%=MOD;
		}
	}
	printf("%lld\n", (dp[N][M]+MOD-1)%MOD);
}