[BOJ 1328] 고층 빌딩 ★

문제 링크

질문은 언제나 환영입니다.

3가지 풀이법이 나오네요. 글에는 없는 자신만의 풀이법이 존재하신다면 알려주세요!

두 가지 풀이법은 $O(n^3)$짜리 풀이이고, 한 가지 풀이법은 $O(n^2)$짜리입니다.

풀이

문제에서 구해야 하는 것은 조건을 만족하는 배치의 수입니다.

세세한 배치의 성질들에 대해 알아볼 방법은 떠오르지 않고, 작은 케이스부터 풀다 보면 패턴이 보이기 때문에 동적 계획법을 시도해볼 수 있습니다.

 

3차원 동적 계획법

$B(x,y,z):=x$개의 빌딩 중 왼쪽에서 $y$개, 오른쪽에서 $z$개만 보이는 경우의 수

위와 같이 정의하는 것은 아주 자연스럽습니다.

 

점화식을 도출할 때는 $B(x-1,\cdots )$와의 관계를 우선 생각 해봅시다.

새로 생긴 가장 긴 막대기를 어디다 꽂아 넣을지를 고민할 수도 있고, 가장 짧은 막대기를 어디다 꽂아 넣을지를 고민할 수도 있습니다.

이 상황에서는 직접 해 보면 후자가 먹힌다는 것을 알 수 있습니다.

 

가장 짧은 막대기는 양 끝이 아니라면 다른 막대기에 가려 $y$와 $z$에 영향을 미치지 않습니다.

따라서 $B(x,y,z)=B(x-1,y,z)+\square$가 되겠군요.

 

남은 경우는 양 끝에 가장 짧은 막대기를 배치하는 것인데, 각 경우에 $y$가 하나 증가하고 $z$가 하나 증가하므로 아래와 같은 점화식을 도출할 수 있습니다.

$B(x,y,z)=B(x-1,y,z)\cdot (x-2)+B(x-1,y-1,z)+B(x-1,y,z-1)$

 

이 점화식을 구현하면 단순하게 $O(n^3)$에 $B(n,l,r)$을 계산하여 문제를 풀 수 있습니다.

 

2차원 동적 계획법

문제에서 주어진 요소를 모두 활용하는 3차원 동적 계획법을 풀긴 했지만, 다소 복잡할 것이라 생각했다면 다른 방식을 시도해 볼 수도 있습니다.

 

문제에서 주어진 상황에서 가장 긴 빌딩을 기준으로 양쪽이 완벽하게 나뉜다는 것을 알 수 있습니다. 따라서 가장 긴 빌딩을 어디로 할 것인지만 정하면 양쪽 각각에서 상대적인 순서 관계를 정해준 뒤, 빌딩들을 배분하면 됩니다.

 

$B(x,y):=x$개의 빌딩 중 $y$개만 보이는 경우의 수

라고 정의한다면, 답은 $\displaystyle \sum _{p=l}^{n-r+1}\binom {n-1}{p-1}\cdot B(p-1,l-1)\cdot B(n-p,r-1)$이 된다는 것을 알 수 있습니다.

 

그럼 $B(x,y)$를 계산하는 방법만 찾으면 됩니다.

가장 긴 빌딩을 어디다가 꽂아 넣을지 정하면 그 뒷쪽에 위치하는 빌딩들의 순서는 중요하지 않고, 가장 긴 빌딩을 기준으로 양쪽이 독립적이라는 점을 이용해 앞선 논리와 같이 다음과 같은 점화식을 세울 수 있습니다.

$\displaystyle B(x,y)=\sum_{i=y}^x B(x-1,y-1)\cdot \frac {(x-1)!} {(i-1)!}$

 

이 점화식을 통해 계산하면 $O(n^3)$만에 문제를 풀 수 있습니다.

 

점화식이 간단한 2차원 동적 계획법

$\displaystyle B(x,y)=\sum_{i=y}^x B(x-1,y-1)\cdot \frac {(x-1)!} {(i-1)!}$은 혼자 $O(n)$을 잡아먹는 다소 복잡한 점화식입니다.

 

만약 가장 긴 빌딩의 위치를 정하는 것이 아니라 가장 작은 빌딩의 위치를 정하는 것이었다면 3차원 동적 계획법에서 점화식을 세웠던 과정과 동일한 논리로 다음의 점화식을 세울 수 있습니다.

$B(x,y)=B(x-1,y-1)+(x-1)\cdot B(x-1,y)$

 

따라서 $O(n^2)$에 문제를 풀 수 있습니다.

코드

3차원 동적 계획법과 점화식이 간단한 2차원 동적 계획법은 그냥 몇 줄 만에 구현이 가능합니다.

따라서 구현이 상대적으로 복잡한 2차원 동적 계획법의 코드만 소개합니다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 103, MOD = 1e9+7;
int n, l, r;
ll dp[N][N];
bool ready[N][N];

#define Add(x,y) x = add(x,y)
#define Mul(x,y) x = mul(x,y)
ll add(ll x, ll y) { return (x=(x+y)%MOD) >= 0 ? x : x+MOD; }
ll mul(ll x, ll y) { return (x=(x*y)%MOD) >= 0 ? x : x+MOD; }
ll pw(ll x, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e%2) r = mul(r,x);
        e /= 2, x = mul(x,x);
    }
    return r;
}
ll inv(ll x) { return pw(x,MOD-2); }

const int F = N;
ll fac[F+1] {1}, caf[F+1];
void precalc() {
    int i = 1;
    for (; i <= F; ++i) fac[i] = mul(fac[i-1],i);
    caf[F] = inv(fac[F]);
    for (i = F; i; --i) caf[i-1] = mul(i,caf[i]);
}
ll C(int n, int k) {
    if (k < 0 or n < k) return 0;
    return mul(mul(fac[n],caf[k]),caf[n-k]);
}

ll calc(int x, int y) {
    // dp[x][y] := x개 중 y개만 보임
    if (x == 0 and y == 0) return 1;
    if (x == 0 or y == 0) return 0;
    if (ready[x][y]) return dp[x][y];
    ready[x][y] = true;
    rep(i,y,x) {
        Add(dp[x][y],mul(calc(i-1,y-1),mul(fac[x-1],caf[i-1])));
    }
    return dp[x][y];
}

int main() {
    precalc();
    scanf("%d %d %d", &n, &l, &r);
    ll ans = 0;
    rep(piv,l,n-r+1) {
        Add(ans, mul(mul(calc(piv-1,l-1),calc(n-piv,r-1)),C(n-1,piv-1)));
    }
    printf("%lld", ans);
}