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

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

 

 

목적

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

 

 

접근법

1. 빌딩을 세우는 과정을 크기가 큰 빌딩부터 작은 빌딩을 하나씩 추가하는 방식으로 진행해보자.

• 다음과 같이 10개의 빌딩이 세워져 있다. 왼쪽과 오른쪽에서 볼 때 각각 3개, 2개가 보인다.

 

• 이러한 경우에 크기가 제일 작은 빌딩 하나를 추가하여 세울 수 있는 경우의 수는 11가지가 된다. 

 

• 하지만 N,L,R만 고려하면 세가지 경우가 나오게 된다. 가장 왼쪽에 배치하면 이전 경우의 L이 1증가하는 경우가 1개 만들어지고, 가장 오른쪽에 배치하면 이전 경우의 R이 1증가하는 경우가 1개 만들어진다. 나머지 가운데에 배치하는 경우는 L또는 R의 변화가 일어나지 않으며 9가지의 경우가 생긴다.

 

2. 이를 통해 점화식을 세울 수 있다. s[i][j][k]를 빌딩이 i개 이고 왼쪽과 오른쪽에서 각각 j개와 k개가 보인다고 정의하면, s[i][j][k]는 s[i-1][j-1][k] + s[i-1][j][k-1] + s[i-1][j][k] x (i-2) 이다.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
int N,L,R,s[101][101][101];

int main(){
    cin>>N>>L>>R;
    s[1][1][1]=1;
    f(i,2,N)f(j,1,L)f(k,1,R)
        s[i][j][k]=((ll)s[i-1][j][k]*(i-2)+s[i-1][j][k-1]+s[i-1][j-1][k])%MOD;
    cout<<s[N][L][R];
    return 0;
}

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.