[BOJ 백준 1328번 - 고층 빌딩] 해설

 

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

1328번: 고층 빌딩

백준 1328번 - 고층 빌딩

문제 설명

상근이가 살고 있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.
상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.
빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오. 

문제 요약

빌딩의 총개수를 N, 왼쪽에서 봤을 때 보이는 빌딩의 수와 오른쪽에서 봤을 때 보이는 빌딩의 수를 각각 L, R이라 하자. N, L, R이 주어졌을 때 가능한 경우를 구하라. 

접근법

먼저 적은 수의 빌딩에 대하여 생각해보자.

//N, L, R = 1, 1, 1

이 경우엔 건물이 오직 하나이기 때문에 왼쪽에서 보거나 오른쪽에서 보거나 모두 1이기 때문에 경우는 한 가지이다. 

이제 N이 2인 경우를 확인해보자. 

//N, L, R = 2, 2, 1

건물이 2개인 경우를 한 가지 생각해보자. 이 경우에는 더 낮은 것이 왼쪽에 있다. 

마지막으로 N이 3인 경우는 두 가지를 확인해보자. 

//N, L, R = 3, 2, 1

//N, L, R = 3, 1, 1

위 과정들을 보면 N-1 상태에서의 건물 배치 사이사이, 또는 양쪽 끝에 제일 작은 건물 하나를 추가하면 N 상태가 됨을 알 수 있다. 
예를 들어 위 N == 2 상태에서 제일 작은 건물을 맨 왼쪽에 배치하면 N, L, R = 3, 2, 1 이 되는 것이고, 두 건물 사이에 배치하면 N, L, R = 3, 1, 1 상태가 되는 것이다. 
이런 식으로 N를 하나씩 늘려나갈 수 있으므로 이 문제는 점화식으로 접근할 수 있다. 

점화식

점화식을 세우기 위해 어떤 경우들이 있는지 보자. 

회색 건물들은 다른 건물들에 가려진다.

첫 번째는 N-1 단계에서 화살표 위치에 제일 작은 건물을 하나 추가하는 것이다. 이때 이 건물은 제일 작은 건물이기 때문에 맨 왼쪽 또는 맨 오른쪽이 아니면 다른 건물들에 의해 가려져 L과 R은 변하지 않고 N 만 1 증가한다. 

 

회색 건물들은 다른 건물들에 가려진다.

두 번째는 맨 오른쪽에 추가하는 것이다. 이 경우에는 오른쪽에서 관측할 때 제일 작은 건물이 추가로 보이기 때문에 R도 1 증가한다. 

세 번째는 맨 왼쪽에 추가하는 것이다. 이 경우에는 왼쪽에서 관측할 때 제일 작은 건물이 추가로 보이기 때문에 L도 1 증가한다. 

N-1개의 건물 배치에서 N개의 건물 배치로 제일 작은 건물을 추가하는 경우는 이렇게 3가지뿐이다. 
1. 중간에 위치 ( 자리는 N-2개 )
2. 맨 오른쪽에 위치 ( 자리는 1개 )
3. 맨 왼쪽에 위치 ( 자리는 1개 )

이를 점화식으로 나타내면 mem[n][l][r] = mem[n-1][l-1][r] + mem[n-1][l][r-1] + (mem[n-1][l][r] * (n-2))이다. 
어느 특정한 (N, L, R)의 경우의 수는 (N-1, L-1, R)에서 맨 왼쪽에 제일 작은 건물 하나 추가하기 + (N-1, L, R-1)에서 제일 오른쪽에 건물 하나 추가하기 + (N-1, L-, R)의 N-2개 중간 지점에 추가하기이다. 

해설 코드

 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007
ll N,L,R,cnt;
ll mem[110][110][110];

ll f(ll n, ll l, ll r) {
    if(l+r>n+1 || l<1 || r<1 || n<1) return 0;
    if(mem[n][l][r] !=-1)return mem[n][l][r];
    if(mem[n-1][l-1][r]==-1) mem[n-1][l-1][r] = f(n-1, l-1, r);
    if(mem[n-1][l][r-1]==-1) mem[n-1][l][r-1] = f(n-1, l, r-1);
    if(mem[n-1][l][r]==-1) mem[n-1][l][r] = f(n-1, l, r);
    mem[n][l][r] = (mem[n-1][l-1][r] + mem[n-1][l][r-1] + (mem[n-1][l][r] * (n-2)))%M;
    return mem[n][l][r];
}

int main() {
    cin>> N >> L >> R;
    memset(mem, -1, sizeof(mem));
    mem[1][1][1]=1;
    cout<< f(N, L, R) << "\n";

}