BOJ 5626 제단

사용한 알고리즘

알고리즘 설명

제단을 만들 수 있는 경우의 수를 모두 찾는 문제이다.
제단이 원래 무엇이었는지를 찾는 형태는 다음과 같다.
제단의 생성 형태에서 높이가 0이 아니라면, 현재 제단의 높이는 앞 뒤와 1이상의 차이가 나서는 안된다.
이러한 형태는 DP로 높이가 증가하거나, 그대로거나, 내려가는 형태 3가지로 만들어 나갈 수 있다.
N이 10000이므로 N * N으로 모든 경우의 수는 계산할 수 없다.
모든 경우의 수가 아닌 제단의 앞에서 부터 모르는 부분에서 생기는 DP 형태를 만들어 나간다.
우리는 모르는 부분의 길이를 찾아서 시작점부터 끝점까지 갈 수 있는 경우의 수를 찾아서 곱해나가면 경우의 수를 찾을 수 있다.

풀이

// baekjoon 5626 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAX_N=10001;
const ll DIV_NUM=1000000007;

int N, start, end, length=1, x;
ll dp[MAX_N], tmp[MAX_N], ret=1;

int main() {
	scanf("%d", &N);
	scanf("%d", &x);
	if (x != -1 && x != 0) return !printf("%d\n", 0);

	for (int i=1; i<N; i++) {
		if (ret == 0) return !printf("%d\n", 0);
		scanf("%d", &x);
		if (x==-1 && i != N-1) length++;
		else {
			if (x == -1) x=0;
			if (i == N-1 && x != 0) return !printf("%d\n", 0);
			memset(tmp, 0, sizeof(tmp));
			tmp[start]=1;
			for (int j=1; j<=length; j++) {
				for (int k=max(0,start-j); k < min(MAX_N, start+j+1); k++) {
					dp[k] = tmp[k];
					if (k-1 >= 0) dp[k] += tmp[k-1];
					if (k+1 < MAX_N) dp[k] += tmp[k+1];
					dp[k] %= DIV_NUM;
				}
				for (int k=max(0,start-j); k<min(MAX_N, start+j+1); k++) tmp[k]=dp[k];
			}
			ret = (ret * dp[x]) % DIV_NUM;
			start = x, length = 1;
		}
	}
	printf("%lld\n", ret);

	return 0;
}