[백준 1328] 고층 빌딩 (C#, C++) - soo:bak

문제 링크

1328번 - 고층 빌딩

설명

높이가 1부터 N까지 모두 다른 빌딩을 한 줄로 배치할 때, 왼쪽에서 L개, 오른쪽에서 R개가 보이는 배치의 경우의 수를 1,000,000,007로 나눈 나머지를 구하는 문제입니다.

접근법

먼저, 높이가 1인 빌딩부터 시작해서 높이가 N인 빌딩까지 하나씩 추가하는 방식으로 생각합니다. 새로 추가하는 빌딩은 현재까지 배치된 빌딩들 중 가장 높으므로, 배치 위치에 따라 보이는 개수가 달라집니다.

다음으로, 새 빌딩을 맨 왼쪽에 놓으면 왼쪽에서 볼 때 새 빌딩이 추가로 보이게 됩니다. 반대로 맨 오른쪽에 놓으면 오른쪽에서 볼 때 새 빌딩이 추가로 보입니다. 가운데 어딘가에 놓으면 양쪽 모두 기존 빌딩에 가려지므로 보이는 개수는 변하지 않습니다.

이후, n개 빌딩을 배치하여 왼쪽에서 l개, 오른쪽에서 r개 보이는 경우의 수는 다음 세 가지의 합입니다. n-1개 배치에서 맨 왼쪽에 추가한 경우, 맨 오른쪽에 추가한 경우, 그리고 가운데 n-2개 위치 중 하나에 추가한 경우입니다.

Code

C#

using System;

namespace Solution {
  class Program {
    const int MOD = 1_000_000_007;

    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split();
      var N = int.Parse(input[0]);
      var L = int.Parse(input[1]);
      var R = int.Parse(input[2]);

      var dp = new long[N + 1, N + 1, N + 1];
      dp[1, 1, 1] = 1;

      for (var n = 2; n <= N; n++) {
        for (var l = 1; l <= n; l++) {
          for (var r = 1; r <= n; r++) {
            var val = 0L;
            val += dp[n - 1, l - 1, r];
            val += dp[n - 1, l, r - 1];
            val += dp[n - 1, l, r] * (n - 2);
            dp[n, l, r] = val % MOD;
          }
        }
      }

      Console.WriteLine(dp[N, L, R] % MOD);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1'000'000'007;

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

  int N, L, R; cin >> N >> L >> R;
  static ll dp[101][101][101];
  dp[1][1][1] = 1;

  for (int n = 2; n <= N; n++) {
    for (int l = 1; l <= n; l++) {
      for (int r = 1; r <= n; r++) {
        ll val = 0;
        val = (val + dp[n - 1][l - 1][r]) % MOD;
        val = (val + dp[n - 1][l][r - 1]) % MOD;
        val = (val + dp[n - 1][l][r] * (n - 2)) % MOD;
        dp[n][l][r] = val;
      }
    }
  }

  cout << dp[N][L][R] % MOD << "\n";

  return 0;
}