Boj 5626 c++ 제단

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

 

정올반 문제이다.

문제

길이가 n인 제단이 주어진다. 제단을 이루는 숫자는 제단의 높이를 뜻한다. 제단이란, 처음과 끝이 0이고, 연속한 두 수의 차이가 1이하인 수열을 뜻한다. 도둑이 훔쳐간 제단열의 높이는 -1로 표시된다.

 

도둑이 훔쳐가 불완전한 제단의 정보가 주어질 때, 가능한 제단의 모양의 경우의 수를 구해야 한다.

 

단, 제단의 길이는 최대 10000이며, 제단열의 높이 또한 최대 10000이다.

관찰&풀이

 

우선 이 문제가 왜 dp로 풀이가 가능한지 생각해보자.

우선 현재 칸의 인덱스가 idx이고 도둑이 훔쳐가 -1로 표시된다고 생각해보면 현재 칸으로 가능한 높이는 총 idx-1개이다.

 

ex) ....................-1(7번째 열) 일 때 해당 칸의 최대 높이는 6이다.

 

도둑이 훔쳐간 칸의 높이를 임의로 h라고 설정했을 때, 이전칸의 높이는 h, h-1, h+1 3가지 중에서 하나일 것이다.

즉, 이전 칸의 높이가 (h-1, h, h+1)일때 가능한 가지수를 모두 합한 값이 현재의 값이기에, 이전 열의 각 높이에서의 경우의 수를

미리 저장해놓는 것이 편하겠다는 직관으로 부터 dp 풀이가 나올 수 있는 것이다.

 

그리고 현재 칸이 훔쳐지지 않았다면 dp[idx][현재칸 높이] 만 업데이트 하고 넘어가면 된다.

 

 

그런데 문제가 하나 발생한다. 

제단열의 높이와 현재까지 고려한 열의 개수를 상태로 잡는다면

10000 * 10000이라서 1억 int 배열 메모리가 잡혀 메모리 초과가 발생할 수 있다.

 

때문에, 현재 점화식에서 이전 값만을 참조하는 특성을 고려하여 토글링을 해주어야 한다.

단, 홀짝이 바뀔 때 이전의 값이 현재 배열에 남아있을 수 있으므로 모두 초기화 시켜줘야 함에 주의해줘야 한다.

 

현재 curr 인덱스 dp 배열에 남아있는 값들은 모두 지금 처음으로 업데이트된 값이어야 하기 때문이다.

 

그리고, 길이가 1인 제단에 대해서도 예외처리를 해주어야 한다.

 

#include <iostream>
#define MOD 1000000007
#define int long long
using namespace std;
int stairs[10010], dp[10010][2];
int32_t main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) { //1base
		cin >> stairs[i];
	}
    if(n == 1) {
        if(stairs[1] > 0)
            cout << "0";
        else
            cout << "1";
        return 0;
    }
	dp[0][1] = 1;
	int curr, pre;
	for(int i = 2; i <= n; i++) {
		curr = i%2;
		pre = (i-1)%2;
		if(stairs[i] == -1) {
			dp[0][curr] = (dp[0][pre] + dp[1][pre] + MOD)%MOD;
			for(int j = 1; j <= i; j++) {
				dp[j][curr] = (dp[j-1][pre] + dp[j][pre] + dp[j+1][pre] + MOD)%MOD;
			}
		} 
		else {
            
			for(int j = 0; j <= i; j++)dp[j][curr] = 0;
            int h = stairs[i];
			if(h == 0) {dp[h][curr] = (dp[1][pre] + dp[0][pre] + MOD)%MOD; continue;}
			dp[h][curr] = (dp[h-1][pre] + dp[h][pre] + dp[h+1][pre] + MOD)%MOD;	
		}
	}
	cout << dp[0][curr];
}