[BOJ 5626 // C++] 제단

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 5626번 문제인 제단이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/5626 

5626번: 제단

문제에서 주어진 제단의 생성과정을 보면, 연속한 두 칸 사이의 높이차는 0 또는 1만 나올 수 있음을 알 수 있다.

 

한편, 맨 처음과 끝의 높이가 0이고 연속한 두 칸의 높이차가 0 또는 1이며 모든 부분의 높이가 0 이상인 모양의 제단은 적절한 생성과정을 통해 항상 만들 수 있다는 것을 관찰하자.

 

이제 dp를 이용해 이전 열까지의, 이전 열의 높이별 경우의 수를 이용해 다음 열까지의, 다음 열의 높이별 경우의 수를 계산해내자.

 

dp[i][h]를 i번째 기둥의 높이가 h인 1~i번 기둥의 배치의 경우의 수로 정의하면 다음과 같은 점화식을 얻을 수 있다.

dp[i][h] = dp[i-1][h-1] + dp[i-1][h] + dp[i-1][h+1]

(단, h가 0인 경우 -1번 인덱스에 접근하지 않게 주의하자.)

 

dp 배열을 할당할 때 dp[10000][10000]사이즈의 배열을 선언하면 문제의 메모리 제한을 넘는 할당을 하게 되므로(약 381MB) 실제로는 나올 수 없는 높이인 5000 이상의 높이는 선언하지 않는 것으로 메모리를 절반으로 커팅하자. 다만 이럴 경우 배열의 인덱스에 5000이상의 높이로 접근하는 시도가 일어나지 않게끔 구현에 신경을 써야한다. (또는 toggling을 해도 좋다.)

 

구현시 모듈로 연산에 유의하자. (이 이유로 한번 틀렸다...)

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int arr[10001];
int dp[10001][5001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		int& x = arr[i];
		cin >> x;
		if (x >= 5000) {
			cout << 0;
			return 0;
		}
	}

	if (arr[1] > 0 || arr[N] > 0) {
		cout << 0;
		return 0;
	}

	dp[1][0] = 1, arr[N] = 0;

	for (int i = 2; i <= N; i++) {
		if (arr[i] == -1) {
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000007;
			for (int k = 1; k < 5000; k++) {
				dp[i][k] = ((dp[i - 1][k - 1] + dp[i - 1][k]) % 1000000007 +dp[i - 1][k + 1]) % 1000000007;
			}
		}
		else {
			if (arr[i] == 0) dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % 1000000007;
			else dp[i][arr[i]] = ((dp[i - 1][arr[i] - 1] + dp[i - 1][arr[i]]) % 1000000007 +dp[i - 1][arr[i] + 1]) % 1000000007;
		}
	}

	cout << dp[N][0];
}