[백준][C++]1328번 고층 빌딩

코딩테스트/백준

[백준][C++]1328번 고층 빌딩

윤깡패 2023. 10. 12. 16:28

문제

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

1328번: 고층 빌딩

상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼

www.acmicpc.net

풀이

점화식 정의

D[N][L][R] : N개의 빌딩이 있고 왼쪽에서 L개, 오른쪽에서 R개가 보일 때 가능할 경우의 수

점화식 도출

: 가장 작은 빌딩 배치

D[N - 1][L - 1][R] : N - 1개의 빌딩에서 왼쪽에 빌딩을 추가할 때 왼쪽 빌딩이 1개 증가
D[N - 1][L][R - 1] : N -1개의 빌딩에서 오른쪽에 빌딩을 추가할 때 오른쪽 빌딩이 1개 증가
D[N - 1][L][R] * (N - 2) : N -1개의 빌딩에서 가운데 빌딩을 추가할 때 증가 수가 없지만, N - 2개의 위치에 배치

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

DP 테이블 초기화

D[1][1][1] = 1

동적 계획법(Dynamic Programming) 알고리즘

동적 계획법(Dynamic Programming) 알고리즘 한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법 동적 계획법 알고리즘 핵심 이론 1. 큰

soobin0821.tistory.com

코드

#include <iostream>
using namespace std;

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

  int N, L, R;
  cin >> N >> L >> R;

  long building[101][101][101] = {0};
  building[1][1][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++)
      {
        building[n][l][r] = (building[n - 1][l - 1][r] + building[n - 1][l][r - 1] + (n - 2) * building[n - 1][l][r]) % 1000000007; 
      }
    }
  }
  
  cout << building[N][L][R];

  return 0;
}

오답

#include <iostream>
using namespace std;

static int N, L, R;
static long mod = 1000000007;
static long D[101][101][101];

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

  cin >> N >> L >> R;
  D[1][1][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++)
      {
        D[i][j][k] = (D[i - 1][j][k] * (i - 2) + (D[i - 1][j][k - 1] + D[i - 1][j - 1][k])) % mod;
      }
    }
  }

  cout << D[N][L][R] << "\n";

}

728x90