백준(BOJ) 5626 제단 **

#DP

재미 있었던 문제

#풀이

점화식은 생각보다 간단하다 높이가 1이 높아지거나,낮아지거나,그대로이거나 3가지 경우이기 때문에

dp[i][k]=dp[i-1][k-1]+dp[i-1][k]+dp[i-1][k+1]인데

문제는 이 문제의 경우 배열로 모든 높이에 대해서 만들어 주게된다면 메모리 초과가 발생한다.

따라서 현재 i의 경우와 바로이전 i-1인 경우에 대해서만 저장해야한다.

dp[1][k]=dp[0][k-1]+dp[0][k]+dp[0][k+1]로 해결했다.

마지막으로 처음과 끝이 무조건 0이기 때문에,

dp[0][0]을 출력해주면 된다.

# 실수 했던 점

첫 입력이 불가능한 경우에 대해서 처리 하지 않았다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 10005
#define INF 987654321
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

ll n,arr[MAX],mem[2][MAX];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
    // 입력을 받는다.
    
    mem[0][0]=arr[1]<1?1:0;
    // 실수한 부분(97%쯤에서 터짐) : 첫 입력이 불가능한 경우 0
    
    for(int i=2;i<=n;i++)
    {
        fill_n(&mem[1][0],MAX,0);
        // mem[0]에는 이전 탑의 경우의 수, mem[1]에는 현재 탑의 경우의 수
        
        if(arr[i]==-1)
        {
            mem[1][0]=(mem[0][0]+mem[0][1])%MOD;
            for(int k=1;k<=MAX/2;k++)
                mem[1][k]=(mem[0][k-1]+mem[0][k]+mem[0][k+1])%MOD;
        }
        else if(arr[i]==0)
            mem[1][arr[i]]=(mem[0][arr[i]]+mem[0][arr[i]+1])%MOD;
        else
            mem[1][arr[i]]=(mem[0][arr[i]-1]+mem[0][arr[i]]+mem[0][arr[i]+1])%MOD;
        // dp[1][k]= dp[0][k-1]+dp[0][k]+dp[0][k+1] 점화식
        
        swap(mem[0],mem[1]);
        // 현재와 이전 탑의 경우의 수 바꿔준다.
    }
    printf("%lld\n",mem[0][0]);
    return 0;
}