고층빌딩

Problem link: https://www.acmicpc.net/problem/1328

DP 솔루션의 점화식을 발견하기 직전까지 갔지만, 근처에서 배회하다가 결국에는 답을 보고 풀었다.

캐시는 아래와 같이 정의한다.

CACHE[bldg][left][right]: [bldg, N] 높이를 갖는 빌딩들을 왼편에서 left개가 보이고 오른편에서 right개가 보이도록 배치하는 경우의 수

점화식은 아래와 같이 구할 수 있다.

CACHE[bldg][left][right] = CACHE[bldg + 1][left - 1][right] + CACHE[bldg + 1][left][right - 1] + CACHE[bldg + 1][left][right] * (N - bldg - 1)

각 항의 의미를 하나씩 살펴보도록 하자.

• CACHE[bldg + 1][left - 1][right]: [bldg + 1, N] 높이를 갖는 빌딩들을 왼편에서 left - 1개가 보이고 오른편에서 right개가 보이도록 배치하는 경우의 수이다. 단순히 제일 왼편에 bldg 높이를 갖는 빌딩을 가져다 놓아주면 CACHE[bldg][left][right]의 경우 중 하나가 될 수 있다.
• CACHE[bldg + 1][left][right - 1]: CACHE[bldg + 1][left - 1][right] 경우와 유사하나 제일 오른편에 빌딩을 가져다 놓아주는 경우이다.
• CACHE[bldg + 1][left][right] * (N - bldg - 1): bldg 높이를 갖는 빌딩이 최우/좌측에 위치하지 않는다면, 이미 놓여져 있는 빌딩 사이사이 어디든 아무데나 넣어주어도 죄/우측에서 바라보는 빌딩 수가 변하지 않는다. 왜냐하면 CACHE[bldg + 1][left][right]의 경우가 세어주는 빌딩의 높이는 모두 bldg보다 높으니까.

구현할 때는 bldg 번호를 큰 놈부터 붙였다.

#include <iostream>
#include <cstdint>

using namespace std;

const size_t kMaxN = 100;
const int64_t kMod = 1000000007;

int64_t CACHE[kMaxN + 1][kMaxN + 1][kMaxN + 1];

int64_t Solve(const int64_t n, const int64_t l, const int64_t r)
{
  CACHE[1][1][1] = 1;
  for (int64_t bldg = 2; bldg <= n; ++bldg)
  {
    for (int64_t left = 1; left <= bldg; ++left)
    {
      for (int64_t right = 1; left + right - 1 <= n; ++right)
      {
        CACHE[bldg][left][right] = CACHE[bldg - 1][left][right] * (bldg - 2);

        if (left >= 2)
        {
          CACHE[bldg][left][right] += CACHE[bldg - 1][left - 1][right];
        }
        if (right >= 2)
        {
          CACHE[bldg][left][right] += CACHE[bldg - 1][left][right - 1];
        }

        CACHE[bldg][left][right] %= kMod;
      }
    }
  }

  return CACHE[n][l][r];
}

int main(void)
{
  int64_t n, l, r;
  cin >> n >> l >> r;
  cout << Solve(n, l, r) << '\n';

  return 0;
}