고층빌딩(DP)

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

1328번: 고층 빌딩

 

빌딩을 어떤 순서로 세우느냐에 집중하기보단 DP를 활용하는 문제인만큼 점화식을 먼저 찾도록 접근하자

다음 배열은 N=10 L=3 R=2에 대한 경우의 수 중 하나이다.

여기서 여태까지 세워진 빌딩보다 가장 작은 빌딩을 하나 추가한다고 생각해보자.

 

빌딩을 추가할 공간은 다음과 같이 11개(현재 빌딩의 수 + 1)가 될 것이다.

 

가장 작은 빌딩을 가장 왼쪽에 추가하는 경우엔

여태까지 세워진 빌딩보다 작다고 했으므로 왼쪽에서 바라보는 빌딩의 갯수가 1개 늘어나게 될 것이다.

즉 해당 경우의 수는 N=11, L=4, R=2에 포함되게 된다.(N+1, L+1, R)

 

가장 작은 빌딩을 가장 오른쪽에 추가하는 경우엔

왼쪽과 동일하게 해당 경우의 수는 N=11, L=3, R=3에 포함되게 된다.(N+1, L, R+1)

 

가장 작은 빌딩을 중간에 추가하는 경우에는

L과 R에는 변화가 없으며 N만 증가하게 된다.(N+1, L, R)

더불어 해당 경우의 수는 빌딩의 갯수 + 1 - 2개만큼 나타난다.(N-2개)

 

이러한 방법을 바탕으로 N개의 빌딩에서 좌우측에서 각각 L, R개가 보이는 빌딩의 경우의 수를 생각한다면

 

N-1개의 빌딩, 각각 L-1, R개가 보이는 경우의 수(N-1개에서 좌측에 추가하는 경우)

N-1개의 빌딩, 각각 L, R-1개가 보이는 경우의 수(N-1개에서 우측에 추가하는 경우)

N-1개의 빌딩, 각각 L, R개가 보이는 경우의 수 * N-2(N-1개에서 중간에 추가하는 경우)

 

이 세 가지 경우의 수를 모두 더한 값이 될 것이다.

 

이것을 점화식으로 나타낸다면

DP[N][R][L] = DP[N-1][L][R ] * (N-2) + DP[N-1][L-1][R] + DP[N-1][L][R-1]

이렇게 도출해낼 수 있다.

 

중간에 곱하는 과정에서 오버플로우가 발생할 수 있으므로 한 번 long long 타입으로 캐스트 해주는 것이 좋다.

마지막엔 문제에서 언급한대로 1000000007으로 %연산을 해준다.

 

#include <iostream>
using namespace std;

int DP[101][101][101] = {0,};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int Size, Left, Right;
	cin >> Size >> Left >> Right;
	DP[1][1][1] = 1;
	for (int i = 2; i <= Size; i++)
	{
		for (int j = 1; j <= Left; j++)
		{
			for (int k = 1; k <= Right; k++)
			{
				DP[i][j][k] = ((long long)DP[i - 1][j][k] * (i - 2) + DP[i - 1][j - 1][k] + DP[i - 1][j][k - 1]) % 1000000007;
			}
		}
	}
	cout << DP[Size][Left][Right] << '\n';
}