[BAE/<JOON> 문제풀이] 1328. 고층 빌딩

www.acmicpc.net/problem/1328

1328번: 고층 빌딩

서론 ||

점화식 다 맞추고 나머지 연산 잘못해서 못풀고 있었다.

 

풀이 ||

특정한 경우의 수를 구하는 문제이므로 Bottom-up 방식이 편하다. (내 기준)

 

각각의 단계마다 사용되는 인자는 총 빌딩갯수, 왼쪽에서 보이는 빌딩 갯수, 오른쪽에서 보이는 빌딩의 갯수 3가지이다.

 

우선 기저 사례는 다음과 같다.

dp[1][1][1] = 1;  // 전체 빌딩이 1개고 왼쪽, 오른쪽에서 보이는 각각의 빌딩이 1개인 경우의 수는 1가지이다.

 

빌딩을 늘려가며 자세히 관찰하다보면 결국 양쪽 방향에서 보이는 빌딩 갯수에 가장 큰 영향을 끼치는 요인은

 

가장 높은 빌딩의 위치라는 점을 발견 할 수 있다.

 

이 점을 이용해서 좀 더 직관적으로 점화식을 설명해보겠다.

 

점화식 ||

우선 길이가 N인 빌딩의 배열이 있을 때, 양쪽에서 보이는 빌딩의 갯수를 (왼쪽)Ns개, (오른쪽)Ne개라고 하고

 

높이가 N인 빌딩의 위치를 Np라고 하자.

 

Ns와 Ne의 최댓값은 각각 Np개, N - Np + 1개이다.

 

그리고 Np를 기준으로 빌딩들을 두 그룹 [LB, RB] 으로 나눴을 때, 빌딩 갯수는 Np - 1개, N - Np개이다.

 

LB그룹은 총 Np - 1개의 빌딩으로 왼쪽에서 봤을 때 Ns - 1개 만큼의 빌딩이 보여야하고,

 

RB그룹은 총 N - Np개의 빌딩으로 오른쪽에서 봤을 때 Ne - 1개만큼의 빌딩이 보여야한다.

(각 그룹에 Np가 빠져있으므로 보이는 빌딩 갯수에서 1을 뺀다.)

 

LB그룹은 오른쪽, RB그룹은 왼쪽에서 보이는 빌딩의 갯수를 고려하지 않으므로 각각의 그룹의 경우의 수는

 

LB경우수 = SUM(DP[Np - 1][Ns - 1]배열의 모든 값)

 

RB경우수 = SUM(DP[N - Np - 1][Ne - 1]배열의 모든 값)

 

 

위의 내용을 정리하면 다음과 같다.

 

DP[i][Ns][Ne] = LB경우수 * RB경우수

 

그런데 아직 한가지 더 곱해야하는 인자가 있다.

 

우리가 위에서 LB그룹 경우의 수와 RB그룹 경우의 수는 상대적인 배치의 경우의 수이다.

높이 5인 빌딩의 위치가 2일 때 , 양쪽 그룹은 각각 1, 3인 길이의 빌딩 배열이다.

나머지 4개의 빌딩을 적절하게 배치하여 오른쪽에서 보이는 빌딩 갯수를 2개로 만들고 싶다.

 

그렇다면 RB그룹의 상대 배치는 1 2 3, 2 1 3 이렇게 2가지가 나온다. 

 

그렇다면 RB경우의 수는 2가지일까? 아니다.

 

4C3 * 2 = (4!/3!*1!) * 2 = 8가지의 경우의 수가 나온다.

각각의 경우의 수에 대해서 이항 계수를 곱해줘야 정확한 빌딩 배치의 경우의 수를 얻을 수 있다.

 

따라서 정확한 점화식은 

 

DP[i][Ns][Ne] = LB경우수 * RB경우수 * 적절한 이항계수(N-1 C LB혹은RB빌딩갯수)

 

가 된다.

 

위의 점화식으로 빌딩 i개에 대한 모든 [양쪽에서 보이는 빌딩의 갯수의 경우(1~Np - 1) | (1~N - Np)] 들을 계산하여 답을 구한다.

 

코드 || ++이 문제는 말로 설명하기가 좀 어려워서 글도 길어졌읍니다... 길게 설명해도 이해가 잘 안갈거 같으니 그냥 코드를 보며 이해 하시는걸 추천합니다...

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

using ull = unsigned long long;

const int MOD = 1000000007;

ull dp[101][101][101];
ull sum[101][101];//sum[i][j] = i개를 사용했을 때 한쪽에서 j개 보이는 빌딩배치의 경우의 수의 합
ull ih[101][101];

int main()
{
	int n, l, r;
	cin >> n >> l >> r;
	ih[0][0] = 1;
	for (int i = 0; i <= n; i++) {
		ih[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			ih[i][j] = ih[i - 1][j] + ih[i - 1][j - 1];
			ih[i][j] %= MOD;
		}
	}

	for (int i = 1; i <= n; i++) {//i : 빌딩 갯수
		dp[i][1][i] = 1;//한쪽에서 i개가 보이는 배치방법은 하나뿐이다.
		dp[i][i][1] = 1;
		for (int j = 2; j < i; j++) {//j : 왼쪽 혹은 오른쪽에서 보이는 빌딩의 갯수
			dp[i][1][j] = sum[i - 1][j - 1];//총 j개 보여야하므로 높이 N인 빌딩 한개 제외
			dp[i][j][1] = sum[i - 1][j - 1];
		}

		for (int j = 2; j < i; j++) {//j : 높이 N인 빌딩의 위치
			int s1 = j;//왼쪽 가시빌딩 갯수
			int s2 = i - j + 1;//오른쪽 가시빌딩 갯수
			for (int k1 = 2; k1 <= s1; k1++) {
				for (int k2 = 2; k2 <= s2; k2++) {
					dp[i][k1][k2] += (sum[s1 - 1][k1 - 1] * sum[s2 - 1][k2 - 1]) % MOD * ih[i - 1][s1 - 1] % MOD; 
					dp[i][k1][k2] %= MOD;
				}
			}
		}
		 
		for (int j = 1; j <= i; j++) {
			for (int k = 1; k <= i; k++) {
				sum[i][j] += dp[i][j][k];//sum 배열 계산해서 채워넣기
				sum[i][j] %= MOD;
			}
		}
	}

	ull dap = dp[n][l][r] != 0 ? dp[n][l][r] : dp[n][r][l];
	cout << dap;
}