BOJ 33801 Game of RUN

문제 링크입니다.

문제 요약

$N$칸짜리 1차원 바둑판에 모든 돌이 잡히지 않도록 적절히 돌을 놓는 방법의 수를 구하세요.

풀이

오른쪽에 칸을 하나씩 추가한다 생각하고 현재 게임판의 상태를 분류합시다. 조건에 맞지 않는 것으로 확정된 게임판을 제외하면 결국 중요한 것은 마지막 칸이 포함된 그룹의 상태 뿐입니다. 따라서 다음과 같이 다섯 가지 상태로 게임판을 분류할 수 있습니다.

1. 마지막 칸이 빈 칸인 경우
2. 마지막 칸에 흰 돌이 들어있고, 그 돌이 포함된 그룹이 빈 칸과 인접해 있는 경우
3. 마지막 칸에 검은 돌이 들어있고, 그 돌이 포함된 그룹이 빈 칸과 인접해 있는 경우
4. 마지막 칸에 흰 돌이 들어있고, 그 돌이 포함된 그룹이 빈 칸과 인접해 있지 않는 경우
5. 마지막 칸에 검은 돌이 들어있고, 그 돌이 포함된 그룹이 빈 칸과 인접해 있지 않는 경우

이때의 상태 전이는 아래 그림과 같이 작동합니다.

이제 위의 상태 전이를 토대로 해 DP로 ${\cal O}(N)$에 $1$부터 $N$까지의 답을 전처리하면 각 테스트 케이스를 ${\cal O}(1)$에 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll mod = 1e9+7;

ll d[1010101][5]; //empty, w solved, b solved, w unsolved, b unsolved

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	d[1][0] = 1;
	d[2][0] = 3;
	d[2][1] = 1;
	d[2][2] = 1;
	d[2][3] = 1;
	d[2][4] = 1;
	for(int i = 3; i <= 1000000; i++){
		d[i][0] = (d[i-1][0]+d[i-1][1]+d[i-1][2]+d[i-1][3]+d[i-1][4])%mod;
		d[i][1] = (d[i-1][0]+d[i-1][1])%mod;
		d[i][2] = (d[i-1][0]+d[i-1][2])%mod;
		d[i][3] = (d[i-1][3]+d[i-1][2])%mod;
		d[i][4] = (d[i-1][4]+d[i-1][1])%mod;
	}
	int T; cin >> T; while(T--){
		int n; cin >> n; cout << (d[n][0]+d[n][1]+d[n][2])%mod << '\n';
	}
}