문제링크
문제
상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다.
상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다.
빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어졌을 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어, N = 5, L = 3, R = 2인 경우에 가능한 빌딩의 배치 중 하나는 1 3 5 2 4이다.
입력
첫째 줄에 빌딩의 개수 N과 가장 왼쪽에서 봤을 때 보이는 빌딩의 수 L, 가장 오른쪽에서 봤을 때 보이는 빌딩의 수 R이 주어진다. (1 ≤ N ≤ 100, 1 ≤ L, R ≤ N)
풀이 유형
풀이
1
2
3
빌딩의 개수 N, 왼쪽에서 본 건물의 수 L, 오른쪽에서 본 건물의 수 R에 대하여,
dp[N][L][R]
= dp[N-1][L-1][R] + dp[N-1][L][R-1] + dp[N-1][L][R]*(N-2)
더해주는 변수 3가지 전부 건물의 개수는 N-1개다. 건물의 개수가 N개가 되기 위해 어떤 N-1개의 건물 보다도 높이가 더 작은 건물을 세울 것이다.
case 1. 왼쪽에서 봤을 때 L-1, 오른쪽에서 봤을 때 R인 경우에 제일 왼쪽.
case 2. 왼쪽에서 봤을 때 L, 오른쪽에서 봤을 때 R-1인 경우에 제일 오른쪽.
위의 두 종류는 직관적으로 이해가 갈 것이다. 하지만 우리는 제일 작은 건물이 기존의 건물 사이, 사이에 들어가는 경우도 생각해주어야 한다.
case 3. 왼쪽에서 L, 오른쪽에서 R일 때 건물 사이에 세우는 경우가 존재한다는 의미다. 이 경우에는, 건물 N-1개의 사이사이 N-2개의 공간에 건물을 세울 수 있을 것이다.
Finally dp[N-1][L-1][R] + dp[N-1][L][R-1] + dp[N-1][L][R]*(N-2)
마무리
풀이는 간단하지만, 생각하기가 다소 어려울 수 있다. 나는 전 단계 보다 큰 건물을 세우는 것을 생각을 했는데 그런 식으로 접근하니 생각하기가 어렵다. 전 단계보다 작은 건물을 세운다는 접근 방식이 다소 어려울 수 있을 것 같다. 특히 조합론 쪽으로 생각을 하기 시작하면, 수렁에 빠진 샘이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long int lli;
int N, L, R;
lli dp[101][101][101];
int main(void){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>N>>L>>R;
memset(dp, 0, sizeof(dp));
dp[1][1][1] = 1;
for(int n = 2; n<= N; n++){
for(int l = 0; l <= n; l++){
for(int r =0; r<= n; r++){
dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r]*(n-2);
dp[n][l][r] %= mod;
}
}
}
cout<<dp[N][L][R]<<endl;
}