| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 6131 | 2085 | 1460 | 31.432% |
문제
상근이가 살고있는 동네에는 빌딩 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)
출력
첫째 줄에 가능한 빌딩 순서의 경우의 수를 1000000007로 나눈 나머지를 출력한다.
접근
수학적으로 식을 구해보려고 했는데, 오랜 시간동안 나오지 않았다.
가장 높은 N 높이의 빌딩을 고정하고 풀면 답이 나오지 않을 것 같았다.
DP 방식의 문제인가 싶어서 점화식을 도출하려 했다.
N의 최댓값이 100이므로, 4차원까지도 식을 세울 수 있었다.
변수가 딱 N, L, R 세개라 arr[N][L][R] = 경우의수 의 테이블로 놓고 생각해보았다.
처음엔 i가 증가할때마다 i 크기의 빌딩을 놓으려고 했는데, 식이 너무 더럽게 나왔다.
발상의 전환이 문제의 핵심이었던 것 같다.
i가 증가할때마다 가장 작은 크기인 1을 (i - 1)번째에 삽입하면,
경우의 수가 크게 3가지로 나뉜다.
- 제일 왼쪽에 놓았을 때 : DP[i - 1][j - 1][k]
- 제일 오른쪽에 놓았을 때 : DP[i - 1][j][k - 1]
- 빌딩 사이에 놓았을 때 : (i - 2) * DP[i - 1][j][k]
( i - 1개의 빌딩에서 1을 삽입하는 것이므로, 빌딩 사이에는 i - 2개의 공간이 있다.)
처음엔 i - 1으로 식을 도출해서 틀렸는데, 다시 생각해보니 바른 식이 나왔다.
풀이
점화식을 그대로 코드로 옮기면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
const ll MOD = 1000000007;
ll dp[101][101][101];
int N, L, R;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
MS(dp, 0);
CIN3(N, L, R);
dp[1][1][1] = 1;
FUP(i, 2, N)
{
FUP(j, 1, L)
{
FUP(k, 1, R)
{
dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + (i - 2) * dp[i - 1][j][k];
dp[i][j][k] %= MOD;
}
}
}
COUT(dp[N][L][R]);
return 0;
}