BOJ 5626 : 제단

5626번: 제단 (acmicpc.net)

5626번: 제단

 

 

시간 복잡도:

• O(N * H/2)

 

알고리즘:

• DP

 

 

 

 

 

말이 꼬여있어서 어렵습니다. 하지만 보면, i번째 제단과 i-1번째 제단 혹은 i+1번째 제단의 차이는 1 이상 날 수 없습니다. 이는 계단 수 문제랑 비슷한데, 변형되었습니다. 조건은 다음과 같습니다.

 

• 시작은 0이여야 합니다. 따라서 1번째 제단의 입력이 0 혹은 -1이 아니라면, 바로 0을 출력합니다.
• 끝 또한 0이여야 합니다.
• i번째 제단이 -1이 아닌 경우 i 빼고 모든 값을 0으로 초기화합니다.
• i번째 제단을 j로 설치하는 경우의 수는 i-1번째를 j, j+1, j-1로 설치하는 경우의 수의 합과 같습니다.

 

여기서 우리는 이 문제가 DP인 것을 손쉽게 알 수 있습니다.

 

하지만 문제가 있습니다. N이 10,000 이고 H의 최댓값 또한 10,000 입니다. 하지만 보듯이, i - 1번째의 값만 알고 있으면 되니, 굳이 2차원으로 만들 필요가 없습니다. 또한, H도 실질적인 최댓값 5,000을 벗어날 수 없습니다. 따라서 우리는 dp 배열을 1차원으로 해서 풀 수 있습니다. (사실 2차원으로 해도 메모리 초과가 안 납니다.)

 

#include <iostream>

using namespace std;
#define int long long
#define MOD 1000000007
#define H 5001

int N, arr[10001], dp[5003][2];

signed main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	if (arr[1] >= 1) { cout << "0" << '\n'; return 0; }
	dp[0][0] = 1; int ptr = 0;
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= H; j++) {
			dp[j][!ptr] = 0;
			if (j != 0) dp[j][!ptr] += dp[j - 1][ptr];
			dp[j][!ptr] += dp[j][ptr] + dp[j + 1][ptr];
			dp[j][!ptr] %= MOD;
			if (arr[i] != j && arr[i] != -1) dp[j][!ptr] = 0;
		}
		ptr = 1 - ptr;
	}

	cout << dp[0][ptr] << '\n';
}