[C++] BOJ 8895 - 막대 배치

BOJ 8895 - 막대 배치 (https://www.acmicpc.net/problem/8895)

01. 🔎 문제 탐색

• 높이가 1-n의 막대가 n개
• 막대를 왼쪽이나 오른쪽에서 봤을 때, 앞의 막대보다 작은 막대가 뒤에 배치되어있을 경우 가려져 보이지 않음
  ({2, 1, 3} 으로 배치되어 있으면, 왼쪽에서 봤을 때, 2와 3 막대만 보여 2개만 보인다는 말)
• 막대 개수: n, 왼쪽에서 보이는 막대 개수: l, 오른쪽에서 보이는 막대 개수: r

01-1. 가능한 시간 복잡도

• n의 최대가 20으로, 시간 복잡도 O(2^N) 이하로 구현 가능

01-2. 알고리즘 선택

• 막대 n개의 높이가 순서대로 주어지므로, DP를 통해 규칙을 찾아 수행할 수 있음
• n이 1일때부터 순차적으로, 다음 블럭이 올 위치를 왼쪽 끝, 오른쪽 끝, 그 외 위치에 배치하여 각 상황에 대한 가지 수를 메모이제이션 할 수 있음
• 단, 길이가 긴 것을 먼저 배치하고 n이 증가함에 따라, 순차적으로 짧은 것을 배치한다고 판단
  (만약 N=4 일 때, 길이가 4인 것부터 배치하고 다음에 3, 2, 1 순서로 배치한다는 뜻)

02. 📝 코드 설계하기

1. n이 1인 경우에는 막대가 하나 이므로, dp[1][1][1]에 대해 1로 초기화
2. n = 2부터 최대인 20까지 l과 r에 대해 반복적으로 메모이제이션을 수행
   1. 다음에 올 막대를 왼쪽 끝에 두는 경우, 왼쪽에서 봤을 때 무조건 1개 더 보이게 되므로 [n-1][l-1][r]의 값을 [n][l][r] 상태에 더해줌
   2. 다음에 올 막대를 오른쪽 끝에 두는 경우, 오른쪽에서 봤을 때 무조건 1개 더 보이게 되므로 [n-1][l][r-1]의 값을 상태에 더해줌
   3. 만약, 다음 막대를 중앙 어딘가에 두려고 할 때, 중앙에 둘 수 있는 가지 수는 양 끝을 제외한 n-2 개의 경우의 수가 있다.
      중앙에 두는 경우, l과 r의 수에 영향이 없으므로, [n-1][l][r] * (n-2) 를 [n][l][r] 에 더해줌
3. n, l, r 을 입력받아, 메모이제이션된 결과를 출력

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

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

ll dp[21][21][21];

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

  dp[1][1][1] = 1;

  for(int n = 2; n <= 20; n++){
    for(int l = 1; l <= n; l++){
      for(int r = 1; r <= n; r++){
        dp[n][l][r] += dp[n-1][l-1][r];
        dp[n][l][r] += dp[n-1][l][r-1];
        dp[n][l][r] += (dp[n-1][l][r] * (n - 2));
      }
    }
  }

  int T;
  int N, L, R;

  cin >> T;
  while(T--){
    cin >> N >> L >> R;
    cout << dp[N][L][R] << "\n";
  }

  return 0;
}