백준 1328: 고층 빌딩

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

 

이 문제는 마주칠때마다 몇 번을 도전했었고, 이제서야 답안을 떠올릴 정도로 난이도가 있는 DP 문제다.

최근에 해결한 DP 문제는 골드 수준이였지만, 이 문제는 간만의 플레티넘 문제여서 아이디어를 떠올리기 힘들었다.

 

모든 높이는 1과 N 사이고, 같은 높이를 가지면 안되므로 1부터 시작해 빌딩의 위치를 정하면 된다.

만약 현재의 빌딩 높이가 h라면, 가장 왼쪽에 두었을 경우, 가장 오른쪽에 두었을 경우, 다른 빌딩에 숨겨진 경우를 구하면 된다.

 

그렇다면 가운데를 기준으로 가장 큰 빌딩부터 순서대로 다른 경우의 수를 구하면 문제가 해결된다.

사실 여기까지는 그렇게 어렵지 않았다. 하지만, 문제는 "다른 빌딩에 숨겨진 경우" 였다. 이것을 어떻게 계산할지가 막막했었다.

 

세워진 빌딩이 하나일 경우엔 이 경우의 수가 없지만, 2채 이상이면 어떻게 구해야 할까? 숨겨진 빌딩의 갯수에 비례해서 구할 순 없을까? 그럼 숨겨진 빌딩 갯수를 카운팅하는 파라미터를 추가할까? 하지만, 추가 파라미터는 공간복잡도를 많이 차지해서, DP를 할 수 없다. 그렇다면, 파라미터들을 활용해 구해보자. 그런데, 답이 아니네...

 

이런저런 생각을 하며, 나는 처음부터 생각을 하기로 했다. 빌딩을 숨길 수 있는 경우는 두 채의 빌딩이 있을 때이다. 이 두채의 빌딩은 이미 둔 빌딩을 활용해야한다. 이미 둔 빌딩은 숨겨진 빌딩 뿐만아니라, 가장 왼쪽에 둔 빌딩, 가장 오른쪽에 둔 빌딩도 포함이다. 그렇다면? 지금까지 둔 빌딩의 사이 만큼 빌딩을 숨길 수 있다는 결론을 내렸다.

 

코드를 구현하며 몇몇 사항에 막혔었는데.

1. 맨 처음의 빌딩은 가장 왼쪽, 오른쪽에 동시에 둘 수 있어서 예외처리를 해야한다.

2. 모든 빌딩을 두어도, 보이는 갯수가 부족하면 갯수를 세지 않는다.

그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
int N, L, R;
ll dp[101][101][101];

ll solve(int n, int l, int r)
{
	if (n == N) return (l == 0 && r == 0);
	ll& ret = dp[n][l][r];
	if (ret >= 0) return ret;
	ret = 0;
	if (l > 0) ret += solve(n + 1, l - 1, r);
	ret %= MOD;
	if (r > 0) ret += solve(n + 1, l, r - 1);
	ret %= MOD;
	ret += (n - 1) * solve(n + 1, l, r);
	ret %= MOD;
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> L >> R;
	memset(dp, -1, sizeof(dp));
	cout << solve(1, L - 1, R - 1) << '\n';
}

한번에 통과를 했지만, 정말 오랜동안 고민했던 문제가 해결되어서 정말 속이 시원한 문제였고, 지금 떠올리면 재밌는 문제였다.