처음으로 도전한 플레티넘 난이도의 DP 문제이다.
DP문제니까 더 작은 문제로 쪼개려고 시도해봤었다.
가장 큰 빌딩이 놓아질 수 있는 범위에서 for문을 돌리면서 왼쪽과 오른쪽에 놓여질 수 있는 빌딩의 수를 줄여가는 방식으로 풀려했었다.
위 과정에서 왼쪽에 올 수 있는 빌딩을 골라주는 과정에서 조합을 이용했고 어찌저찌 아이디어는 맞는 거 같아서 2시간 동안 시도하다가 구현 실패로 그냥 구글링했다 ㅠㅠ
힘겹게 풀이 아이디어를 떠올려도 구현하는 게 요즘 정말 어렵더라 ㅠㅠ 게다가 이 아이디어가 맞다는 보장도 없다...
풀이는 아래 고수분의 블로그를 참고하였다.
https://beginthread.tistory.com/151
문제링크
https://www.acmicpc.net/problem/1328
설명
빌딩의 개수를 N개, 왼쪽에서 보이는 빌딩의 개수를 L개, 오른쪽에서 보이는 빌딩의 개수를 R개이라 하고, 이를 만족하는 경우의 수를 dp[N][L][R]이라 하자.
빌딩의 개수가 N - 1개인 상황에서 위 식을 만족하는 경우의 수를 생각해보자.
우선 N - 1개의 빌딩은 새로 놓을 1개의 빌딩보다 모두 높다고 생각하자.
다른 고수 분의 블로그에 따르면 항상 높이가 1인 빌딩을 추가해가고 이를 추가하면서 기존에 있던 빌딩의 높이는 1씩 증가한다고 생각하면 더욱 이해가 잘 된다고 한다.
1) dp[N - 1][L - 1][R]
위 상황에서 높이가 1인 빌딩을 맨 왼쪽에 추가한다고 생각해보자.
맨 왼쪽에 가장 작은 빌딩이 하나 추가됐기 때문에 L은 1 증가할 것이다.
그렇다면 dp[N][L][R]의 경우의 수가 된다.
2) dp[N - 1][L][R - 1]
위 상황도 1)과 똑같다. 높이가 1인 빌딩을 맨 오른쪽에 추가한다면 dp[N][L][R]의 경우의 수가 된다.
3) (N - 2) * dp[N - 1][L][R]
위 상황을 생각해보자.
우리는 높이가 1인 빌딩을 추가할 것이고 이 빌딩은 기존에 존재한 그 어느 빌딩보다 작다.
즉, 맨 왼쪽과 오른쪽을 제외한 사이에 이 빌딩을 추가한다면 전체 빌딩의 개수는 1 증가하겠지만, 왼쪽과 오른쪽에서 보이는 빌딩의 개수는 변하지 않는다!
또한 높이가 1인 빌딩을 추가하는 경우의 수는 N - 2가지이다.
위 3가지 과정을 통해 우리는 다음과 같은 점화식을 생각해 낼 수 있다.
dp[N][L][R] = dp[N - 1][L - 1][R] + dp[N - 1][L][R - 1] + (N - 2) * dp[N - 1][L][R]
위 점화식을 이용해서 dp[N][L][R]을 구할 수 있다.
막상 다른 분들의 코드를 보면 정말 간단한 한 줄짜리 점화식이라고 생각할 수 있지만, 이를 내가 혼자 힘으로 생각할 수 있을까...? 라는 생각을 하면 암울해진다...
그래도 접근하는 방식은 좋았다고 생각한다...!
오늘도 이렇게 정신승리를 한다...
계속 이렇게 PS하다보면... 저런 생각도 할 수 있는 날이 오겠지...! 파이팅...!!
코드
#include <iostream>
#define mod 1000000007
using namespace std;
int N, L, R;
long long dp[101][101][101];
void input()
{
cin >> N >> L >> R;
}
void solution()
{
dp[1][1][1] = 1;
for (int i = 2; i <= N; i++) // 건물의 개수
for (int j = 1; j <= i; j++) // 왼쪽에서 보이는 건물의 개수
for (int k = 1; k <= i; k++) // 오른쪽에서 보이는 건물의 개수
dp[i][j][k] = (dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i - 1][j][k] * (i - 2)) % mod;
// dp[i][j][k]는 다음과 같이 쪼갤 수 있다.
// dp[i - 1][j - 1][k]에서 가장 작은 건물 하나를 맨 왼쪽에 추가하면 dp[i][j][k]가 된다.
// dp[i - 1][j][k - 1]에서 가장 작은 건물 하나를 맨 오른쪽에 추가하면 dp[i][j][k]가 된다.
// dp[i - 1][j][k]에서 가장 작은 건물을 기존에 있는 건물 사이에 추가한다면 dp[i][j][k]가 된다. + 이러한 경우가 (i - 2)개가 있다.
cout << dp[N][L][R];
}
void solve()
{
input();
solution();
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}