백준 8895번 막대 배치 1328번 고층 빌딩

이 글에서 다룰 문제는 백준 8895번 막대 배치와 1328번 고층 빌딩이다. 두 문제는 주어지는 입력의 범위 정도만 다르고 거의 같은 문제라고 볼 수 있다. 8895번 막대 배치 문제를 중점적으로 설명하고 1328번 고층 빌딩 문제는 차이점을 기준으로 간단히 언급하는 식으로 진행하겠다.

문제

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

8895번: 막대 배치

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

1328번: 고층 빌딩

풀이

막대의 개수가 \(n\), 왼쪽에서 보이는 막대의 개수가 \(l\), 오른쪽에서 보이는 막대의 개수가 \(r\)이라고 할 때, 막대를 배치하는 경우의 수를 \(dp\left(n,l,r\right)\)라고 하자. 점화식을 구하기 위해서는 경우를 나누어서 생각해 보아야 한다. 길이가 서로 다른 \(n-1\)개의 막대 사이에 가장 짧은 막대를 끼워 넣는 상황을 가정하자. 또는 높이가 \(1,2,\dots,n-1\) 인 막대를 배치하는 모든 경우를 알고 있을 때, 막대의 높이를 모두 \(1\)씩 증가시키고 높이가 \(1\)인 새로운 막대를 끼워 넣어서 조건을 만족하는 경우의 수를 구한다고 생각해도 좋다. 우선 길이가 가장 짧은 막대(또는 길이가 \(1\)인 막대)를 보이게 배치하는 경우와 보이지 않게 배치하는 경우로 나누어서 생각해보자.

 

길이가 가장 짧은 막대가 보이게 배치하는 경우

기존의 막대들은 모두 새로 끼워넣는 막대보다 길이가 길다. 따라서 길이가 가장 짧은 막대를 보이게 하기 위해서는 막대를 가장 왼쪽에 위치시키거나 가장 오른쪽에 위치시켜야 한다.

길이가 가장 짧은 막대를 왼쪽 끝에 위치시키는 경우의 수: \(dp\left(n-1,l-1,r\right)\)

길이가 가장 긴 막대를 오른쪽 끝에 위치시키는 경우의 수: \(dp\left(n-1,l,r-1\right)\)

 

길이가 가장 짧은 막대가 보이지 않게 배치하는 경우

길이가 가장 짧은 막대를 보이지 않게 배치하기 위해서는 \(n-1\)개의 막대를 왼쪽에서 \(l\)개, 오른쪽에서 \(r\)개가 보이도록 배치해 둔 후 기존의 막대 사이에 새로운 막대를 끼워 넣으면 된다. 막대를 끼워 넣을 수 있는 위치의 수는 \(\left(n-2\right)\)이므로 길이가 가장 짧은 막대를 보이지 않게 배치하는 경우의 수는 \(\left(n-2\right) \times dp\left(n-1,l,r\right)\)이다.

 

이를 모두 더해서 점화식으로 나타내면 다음과 같다.

\[ dp\left(n, l, r \right) = dp\left(n-1,l-1,r\right) + dp\left(n-1,l,r-1\right) + \left(n-2\right)dp\left(n-1,l,r\right) \]

 

이제 점화식의 초기 조건을 구해 보자. 문제의 예제 입력을 보면 배치가 불가능한 경우도 입력으로 들어오는 것을 확인할 수 있다. 배치할 수 없을 때의 경우의 수는 \(0\)이며 이를 고려하여 초기 조건을 설정할 필요가 있다. 우선 가장 기본적인 상황을 살펴보겠다. 막대의 개수 \(n=1\), 왼쪽에서 보이는 막대의 개수 \(l=1\), 오른쪽에서 보이는 막대의 개수 \(r=1\)인 상황을 생각해보자. 길이가 \(1\)인 막대 한 개를 배치할 때 이 상황을 만족시키며, 이 때의 경우의 수는 \(1\)이라는 것을 알 수 있다. 따라서 \(dp\left(1, 1, 1\right)=1\)이다. 이제 \(n=0\) 또는 \(l=0\) 또는 \(r=0\)인 상황을 생각해 보자. 이러한 상황은 불가능하다는 것을 알 수 있다. 그러므로 \(n,l,r\)중에 \(0\)인 값이 하나라도 있다면 그때의 경우의 수는 \(0\)으로 설정한다. 물론 \(n=l=r=0\)인 경우는 가능한 경우로 볼 수 있다. 그렇다면 조합에서 \({n \choose 0} = 1\)인 것처럼 \(dp\left(0,0,0\right)=1\)이 되어야 하지 않을까? 그러나 이 문제의 경우 점화식에서 확인할 수 있듯이 양의 정수 \(n,l,r\)이 동시에 \(0\)이 되는 경우는 존재하지 않는다. \(n,l,r\) 중 일부는 \(0\)이고 일부는 양수인 경우는 불가능 하다는 것이 자명하고, 재귀식을 풀어 나가다 보면 \(n,l,r\)이 모두 \(0\)이 되기 전에 일부가 \(0\)이 되거나 모두 \(1\)이 되어 종료된다. 따라서 이 문제에서 \(n=l=r=0\)일 때의 경우의 수에 대해서는 고려하지 않아도 된다.

 

문제에서 입력으로 주어지는 \(n,l,r\)은 모두 양의 정수이다. 위의 점화식을 보면 \(n, l, r\)이 \(1\)씩 감소하며 계산이 이루어 진다는 것을 확인할 수 있다. 그러므로 계산을 진행하다 보면 언젠가는 \(n=1,l=1,r=1\)에 도달하거나 \(n, l, r\)중 한 값이 \(0\)이 될 것이다. 초기 조건에 걸리지 않고 \(n,l,r\) 중에 음수인 값이 발생하여 계산이 제대로 이루어지지 않는 일이 생기지는 않을까? \(n, l, r\)은 모두 1씩 감소하므로 음수가 되기 전에 반드시 \(0\)을 거치게 된다. 따라서 초기 조건을 거치치 않고 음수가 되는 경우는 존재하지 않는다.

 

초기 조건까지 고려하면 \(dp\left(n, l, r\right)\)을 다음과 같이 나타낼 수 있다.

\[ dp\left(n,l,r\right)=\cases{ 1\qquad\text{if } n=1 \text{ and } l=1 \text{ and } r=1 \\ 0\qquad\text{if } n=0 \text{ or } l = 0 \text{ or } r = 0 \\ dp\left(n-1,l-1,r\right) + dp\left(n-1,l,r-1\right) + \left(n-2\right)dp\left(n-1,l,r\right)\quad\text{otherwise } }\]

 

3차원 dp배열을 계산을 통해 모두 채운다고 생각하면 시간 복잡도는 \(O\left(nlr\right)\)이다. 문제의 입력 조건을 고려해보았을 때 충분하다는 것을 알 수 있다.

소스코드

8895번 막대 배치 문제의 코드이다. 입력값은 작지만 출력값은 \(2^{31}-1\)보다 커질 수 있으므로 주의해야 한다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

const int MAX = 21;
ll dp[MAX][MAX][MAX];

ll f(int n, int l, int r) {
    if (dp[n][l][r] != -1) return dp[n][l][r];
    if (n == 0 or l == 0 or r == 0) return dp[n][l][r] = 0;
    return dp[n][l][r] = f(n-1, l-1, r) + f(n-1, l, r-1) + (n-2)*f(n-1, l, r);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    memset(dp, -1, sizeof dp);
    dp[1][1][1] = 1;
    int T;
    cin >> T;
    while (T--) {
        int n, l, r;
        cin >> n >> l >> r;
        cout << f(n, l, r) << '\n';
    }
    return 0;
}

 

1328번 고층 빌딩 문제의 코드이다. 이 문제를 처음에 보고 1027번 고층 건물 문제가 생각이 났다. 그러나 1328번에서는 위치와 각도에 따라 건물이 보이거나 보이지 않을 수 있다는 점은 고려하지 않아도 된다. 막대 배치 문제와 거의 동일하지만 테스트케이스가 하나만 들어오는 대신 \(n,l,r\)의 범위가 증가하였다. \(1000000007\)로 나눈 나머지를 구해야 한다는 것을 고려해서 구현해 주면 된다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

const int MAX = 101;
const ll MOD = 1000000007;
ll dp[MAX][MAX][MAX];

ll f(int n, int l, int r) {
    if (dp[n][l][r] != -1) return dp[n][l][r];
    if (n == 0 || l == 0 || r == 0) return dp[n][l][r] = 0;
    return dp[n][l][r] = (f(n-1, l-1, r) + f(n-1, l, r-1) + (n-2)*f(n-1, l, r)) % MOD;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    memset(dp, -1, sizeof dp);
    dp[1][1][1] = 1;
    int N, L, R;
    cin >> N >> L >> R;
    cout << f(N, L, R) << '\n';
    return 0;
}