5626 - 제단

문제 링크

---

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

문제 요약

---

현재 제단의 상태가 주어진다. 도둑이 훔쳐간 부분은 -1이고 남아있는 부분은 정수로 표현이 되어있다.  이 때 가능한 초기 제단의 경우의 수를 구하는 문제다. 문제에서 초기 제단을 만드는 방법은 주어진다.

문제 풀이

---

모든 열의 초기값은 0이다. 이 때 한가지 연산을 할 수 있다. 같은 높이를 가지는 연속하는 열들을 선택한다. 그리고 선택한 연속된 열 중 처음 열과 가장 끝 열을 제외한 모든 열의 높이를 1씩 높인다. 이 연산을 사용해서 제단을 만들어 나갈 수 있다. 이 연산을 잘 생각해 본다면 두가지 통찰을 얻을 수 있다.

1. 첫 번째 제단과 마지막 열의 높이는 0이다.

2. 인접한 두 열의 높이차는 최대 1이다.

이 두가지 통찰을 이용해 우리는 \(dynamic\ programming\)을 설계할 수 있다. \(dp\)식은 아래와 같다.

\(dp[i][j]\) : \(i\)번 째 열의 높이가 \(j\)일 경우의 수(첫 번째 열부터 순서대로 높이를 결정해 나갈 때)

그렇다면 \(dp\)식은 어떻게 계산이 될까? \(dp[i][j]\)는 위에서 언급한 두 번째 통찰에 의해 쉽게 계산이 가능하다. 인접한 두 열의 높이차는 최대 1까지 가능하으로 \(dp[i][j]\)는 \(dp[i - 1][j - 1],\ dp[i - 1][j],\ dp[i - 1][j + 1]\)의 합이 된다. 

한가지 유의할 점은 \(i\)의 값에 따라 \(j\)가 결정이 될때도 있고 안될때도 있다는 것이다. \(A[i]\)의 값이 -1이라면 \(j\)는 1부터 \(n\)까지 가능할 것이다. 하지만 \(A[i]\)값이 음이 아닌 정수라면 \(j\)는 A[i]를 제외 하고는 전부 0이 되어야 한다.

자 이제 우리는 완벽하게 답이 나오는 \(dp\)식을 설계했지만 아쉽게도 메모리 제한으로 인해 \(ML\)을 받는다. 이러한 점을 개선할 수 있을까? \(dp\)식을 개선해 본다면 \(i\)번째 테이블을 계산할 때 \(i-1\)번째 테이블만 필요하다는 것을 알 수 있다. 이 점을 이용해 슬라이딩 윈도우를 적용한다면 최종적으로 정답을 받을 수 있다.

소스 코드

---

#include <stdio.h>
#include <string.h>

typedef long long ll;

const ll mod = 1000000007;
int n, A[10010];
ll dp[2][10010];

int main() {
  scanf("%d", &n);
  for (int i = 0 ; i < n ; ++i) {
    scanf("%d", &A[i]);
    if (A[i] != -1) {
      ++A[i];
    }
  }
  
  int t = 1;
  dp[0][1] = (A[0] == -1 || A[0] == 1) ? 1 : 0;
  for (int i = 1 ; i < n ; ++i, t = 1 - t) {
    memset(dp[t], 0, sizeof(dp[t]));
    if (A[i] == -1) {
      for (int j = 1 ; j <= n ; ++j) {
        dp[t][j] = (dp[1 - t][j - 1] + dp[1 - t][j] + dp[1 - t][j + 1]) % mod;
      }
    } else {
      dp[t][A[i]] = (dp[1 - t][A[i] - 1] + dp[1 - t][A[i]] + dp[1 - t][A[i] + 1]) % mod;
    }
  }
    
  printf("%lld\n", dp[1 - t][1]);
}