PS#8 [1328번 - 고층 빌딩]

pengooseDev·2023년 6월 13일

1328번 3차원 배열 DP 백준

빌딩 높이만 나오면 stack이 생각나서 처음에 stack으로 접근했으나 dp문제였다.
A1, A2, A3, . . . , Ai, . . . An

n개의 건물을 일렬로 늘어놓자.
단, A1이 가장 왼쪽, An이 가장 오른쪽이라고 가정한다.

DP를 풀 때, 주관적인 주의사항

DP문제의 관건은 점화식이다.
수능 수학을 좋아했던 사람이라면, 귀납적 추론을 통한 일반항을 도출에 익숙할 것이다.

DP에 사용되는 점화식을 효과적이고 효율적으로 추론하기 위해 두 가지 사항을 주의해야한다.

첫 번째 주의사항

반드시 n번째 항은, 이전 항(n - 1, n - 2, . . . )에 종속적으로 시행되어야 한다.

어찌보면 당연하지만, 위의 사항을 고려하지 않고 접근한다면, 잘못된 접근하거나 DP 함수를 짜기에 난이도(너무 많은 분기처리 등)가 지나치게 높아질 수 있다.

두 번째 주의사항

초항을 제대로 고려하였는가?

DP 문제에서 WA의 원인을 살펴보면 생각보다 초항을 제대로 고려하지 않은 경우가 종종 있다.
이 1328번 문제 또한, 초항의 특성을 잘 고려해서 첫 단추를 잘 끼워야 점화식을 추론하기 간편했다.

+a

DP중에 애드혹스러운 문제가 종종 존재한다. 삼각형 모양 DP를 왼쪽으로 정렬하고 빈 칸에 0을 넣는 것이 대표적인 예시이다. 직관적인 접근법일수록 답안을 추론하기 간편하다.

첫 번째 주의사항에 연결되는 부분으로, 이전 항에 종속적인 시행이 되도록 점화식을 짜면 애드혹스러운 문제를 파훼할 수 있는 경우도 존재한다.

접근법

위의 주의사항에 근거하여, 점화식을 세워보자.
해당 문제에서 고려해야하는 사항은 아래와 같다.

1. 현재 빌딩이 몇 개인가?

빌딩의 갯수는 n개가 주어진다.

1개 => 2개 => 3개 => . . . => n개

2. 왼쪽에서 보았을 때, 건물이 몇 개인가?

3. 오른쪽에서 보았을 때, 건물이 몇 개인가?

위 사항을 고려해서 DP 배열을 생성하자.
DP배열은 3차원 DP배열이다.
i : 현재 빌딩 개수.
j : 왼쪽에서 보았을 때, 건물 개수.
k : 오른쪽에서 보았을 때, 건물 개수.

dp[i][j][k]

그렇다면 초항은?

건물이 하나(A1)일 때는, 왼쪽에서 보나, 오른쪽에서 보나 보이는 건물은 하나이다.
따라서, dp[1][1][1] = 1;이다.

점화식 추론

그렇다면 이전항에 어떻게 종속적으로 영향을 받는가?
경우의 수는 3가지이다.

1. dp[i - 1][j - 1][k]

i - 1개의 빌딩이 있을 때, 왼쪽에서 j - 1개. 오른쪽에서 k개가 보이는 경우의 수.
가장 왼쪽에 새로운 빌딩을 추가하면 왼쪽에서 보이는 빌딩이 하나 늘어난다.

2. dp[i - 1][j][k - 1]

i - 1개의 빌딩이 있을 때, 왼쪽에서 j개. 오른쪽에서 k - 1개가 보이는 경우의 수.
가장 오른쪽에 새로운 빌딩을 추가하면 오른쪽에서 보이는 빌딩이 하나 늘어난다.

3. dp[i - 1][j][k] * (i - 2)

새로운 빌딩을 가장 오른쪽이나 왼쪽이 아닌, 가운데 어딘가(2 ~ n - 2)에 추가하는 경우의 수.
오른쪽과 왼쪽에서 보이는 빌딩의 수는 유지.
현재 i개의 건물 중, 가장 오른쪽과 가장 왼쪽의 빌딩을 제외한 i - 2개의 위치에 새로운 빌딩을 배치할 수 있다.

이전 항(i - 1)에서 위 모든 경우의 수를 합하여 다음 항(i)을 추론한다.

dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i - 1][j][k] * (i - 2);

코드

#include <iostream>
using namespace std;

int MOD = 1000000007;
long long dp[101][101][101];

int main()
{
  int N, L, R;
  cin >> N >> L >> R;

  dp[1][1][1] = 1;
  for (int i = 2; i <= N; i++)
    for (int j = 1; j <= L; j++)
      for (int k = 1; k <= R; 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;

  cout << dp[N][L][R] << endl;

  return 0;
}