[BOJ 1328] 고층 빌딩

[BOJ 1328] 고층 빌딩

[BOJ 8895] 막대 배치 (위 문제와 거의 비슷함)

4일, 시간으로 따지면 7시간 정도 고민한 문제인데 풀릴 듯 안 풀려서 솔루션을 찾아보았다. dp테이블의 의미까지는 dp[n][l][r]=a n번째 막대까지 왼쪽에서 봤을 때 l개, 오른쪽에서 봤을 때 r개일때 가능한 경우의 수 a가지 까지는 똑같이 생각했으나 나머지 점화식을 떠올리지 못했다. 풀이의 핵심은 막대의 길이를 내림차순(긴 막대 -> 짧은 막대)으로 본다는 것이었다. 

만약 현재 dp[i][l][r]의 테이블을 채우기 위해서는 이전 막대의 l과 r이 1 작은 값의 경우의 수와 일치한다는 것이다. 이게 가능한 이유는 막대를 내림차순으로 사용하기 때문에, 현재 사용한 막대는 반드시 이전 막대들보다 짧다는 확신이 있기 때문이다. 그래서 현재 막대를 맨 왼쪽에 배치한다면 왼쪽에서 보이는 막대가 1개 늘어나게 되고 오른쪽의 경우도 마찬가지이다. 또한 현재 막대들 사이에 놓는 경우도 고려해야 하는데 이 역시 현재 막대는 다른 막대보다 짧다는 확신이 있기 때문에 l,r값에는 영향이 없고 그렇게 배치할 수 있는 경우의 수는 총(i-2)가지이다. 전체적으로 풀이가 약간 라인스위핑같은 느낌이었다.

#include<stdio.h>
#define MOD 1000000007
typedef long long ll;
ll dp[111][111][111];
 
int main(){
    int n,l,r;    scanf("%d %d %d",&n,&l,&r);
 
    dp[1][1][1]=1;
    dp[2][1][2]=1,dp[2][2][1]=1;
 
    for(int i=3 ; i<=n ; i++){
        for(int lll=1 ; lll<=i ; lll++){
            for(int rrr=1 ; rrr<=i ; rrr++){
                dp[i][lll][rrr]+=dp[i-1][lll-1][rrr];
                dp[i][lll][rrr]+=dp[i-1][lll][rrr-1];
                dp[i][lll][rrr]+=dp[i-1][lll][rrr]*(i-2);
 
                dp[i][lll][rrr]%=MOD;
            }
        }
    }
 
    printf("%lld\n",dp[n][l][r]);
    return 0;
}