[백준] 5626 - 제단

www.acmicpc.net/problem/5626

5626번: 제단

 문제 설명이 너무 불친절하다. 이해하는데만 한참이 걸렸다. 동적계획법/DP 문제다. DP는 점화식을 세우는게 관건인데, 이게 문제마다 점화식을 도출하는 방식이 워낙 다양하다보니 잘하는데에 왕도가 없다. -_-;;; 그냥 많이 풀어보는 것 밖에는 답이 없는 듯...

 이 문제는 DP의 사이즈를 제단의 사이즈만큼 모두 잡아버리게 되면 10000 x 5000 x 4 바이트의 저장공간이 필요하게 되는데 이러면 메모리 초과가 난다. 그래서 점화식을 세우면서 메모리를 절약하는 방법에 대한 고민을 해결하는게 포인트다. N번째 제단 열에서 가능한 제단의 수를 구할때는 N-1번째, 즉 이전 제단 열에서 가능한 제단의 경우의 수만 알면 되기 때문에, 이부분에서 착안하면 2 x 5000 x 4 바이트의 저장공간만을 이용하고도 답을 구할 수 있다.

 N번째 열의 K높이의 제단이 주어질 때, 이 위치에 제단이 있을 수 있는 경우의 수를 점화식으로 구하면 아래와 같다. 결국 제단의 높이는 이전 열의 제단 높이에서 한칸이 높아지거나, 같거나, 낮아지거나 3가지 경우 밖에 없기 때문이다.

dp[N][K]=dp[N-1][K-1]+dp[N-1][K]+dp[N-1][K+1]

 

 소스는 아래와 같다.

#include <stdio.h>
#define MIN(A, B) (((A) < (B)) ? (A) : (B))

int podium[10001];
int dp[2][5001];
int main()
{
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &(podium[i]));
        if (podium[i] > MIN(i, (N - 1) - i))
        {
            printf("0\n");
            return 0;
        }
    }

    dp[0][0] = dp[1][0] = 1;

    for (int i = 0; i < N; ++i)
    {
        int cur = i % 2;
        int pre = (cur + 1) % 2;
        for (int x = 0; x < (N+1) / 2; ++x)
            dp[cur][x] = 0;

        if (podium[i] == -1)
        {
            for (int x = 0; x < (N+1) / 2; ++x)
            {
                if (x > MIN(i, (N - 1) - i))
                    break;

                for (int k = -1; k < 2; ++k)
                {
                    int prex = x + k;
                    if (prex < 0)
                        continue;

                    dp[cur][x] += dp[pre][prex];
                    dp[cur][x] %= 1000000007;
                }
            }
        }
        else
        {
            for (int k = -1; k < 2; ++k)
            {
                int prex = podium[i] + k;
                if (prex < 0)
                    continue;

                dp[cur][podium[i]] += dp[pre][prex];
                dp[cur][podium[i]] %= 1000000007;
            }
        }
        if (i == N - 1)
            printf("%d\n", dp[cur][0] % 1000000007);
    }

    return 0;
}