[BOJ] 1328 : 고층 빌딩

문제 링크

1328번: 고층 빌딩 (acmicpc.net)

1328번: 고층 빌딩

왼쪽에서 본 빌딩의 개수와 오른쪽에 본 빌딩의 개수가 주어졌을 때 가능한 빌딩 배치의 경우의 수를 구하는 문제.

 

참고 링크

https://beginthread.tistory.com/151

[ BOJ 백준 1328번 - 고층 빌딩 ] 해설 및 코드

 

풀이

시작전에, 플레티넘 문제라는 것에 색안경이 씌워져 두려움부터 갖고 시작했다. 그러다보니 아이디어가 더욱 잘 떠오르지않아 결국 다른 고수분의 아이디어를 참고해서 풀었다.

공부한다는 마음으로 아이디어를 내 방식으로 다시 적어보려한다.

◆빌딩은 높은 빌딩부터 낮은 빌딩순으로 배치한다고 생각한다.

현재까지 빌딩이 이렇게 배치되어있다고 해보면, 총 10개의 빌딩이 세워져있고 왼쪽에서 봤을 때 3개 오른쪽에서 봤을 때 2개가 보이는 상황이다.

빌딩은 높이를 기준으로 높은 빌딩부터 배치한다고 했으므로, 다음 세울 빌딩은 가장 낮은 빌딩이 될 것이다.

새로운 빌딩이 들어갈 수 있는 경우의 수는 총 11가지이다. 11가지를 L과 R에 따라 3가지로 분류해보면

1. 맨 왼쪽에 설치를 하게 될 경우 L = 4로 바뀌고 R = 2로 유지된다.

2. 가운데에 설치 할 경우 L = 3, R = 2 모두 그대로 유지된다.

여기서 가운데라는 것은 양끝을 제외한 나머지 모든 구역이다. 따라서 가운데 = 11 - 2(양끝) = 9가지.

3. 맨 오른쪽에 설치 할 경우 L = 3으로 유지되고, R = 3로 바뀐다.

DP 배열의 인덱스를 DP[N][L][R] 로 설정하면

점화식은 DP[i][j][k] = DP[i-1][j-1][k] + DP[i-1][j][k] * (i-2) + DP[i-1][j][k-1] 로 세울 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
 
const int INF = INT_MAX;
const int MAX_N = 100 + 5;
ll DP[MAX_N][MAX_N][MAX_N];
int N, L, R;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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] << "\n";
}

플레티넘 문제도 자신있게 풀면 풀 수 있을 것 같다는 느낌을 준 문제다.

사진 사용하게 해주신 재미지님 감사합니다!