백준 No.1328 [고층 빌딩]

Baekjoon Online Judge No.1328 [고층 빌딩]

---

 문제 

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

1328번: 고층 빌딩

---

 설명 

핵심 변수 : unsigned long long city[N][L][R];

 

  N개의 빌딩이 있고, 좌측에서는 L 개의 빌딩, 우측에서는 R 개의 빌딩이 보일 때 경우의 수의 값을 의미한다.

 

  city[1][1][1] 은 1개의 빌딩이 있고, 좌측에서는 1개의 빌딩, 우측에서는 1개의 빌딩이 보이는 경우의 수의 값을 의미한다. 이 경우엔 그냥 건물이 한 채 있는 경우이므로 city[1][1][1] == 1 이 된다.

 

  우리는 이 값을 토대로 city[2][2][1] 과 city[2][1][2] 의 값을 구할 수 있다. 

 

city[2][2][1] // 2개의 빌딩이 있는 경우, 좌측에서는 2개의 빌딩, 우측에서는 1개의 빌딩이 보이는 경우의 수 city[2][1][2] // 2개의 빌딩이 있는 경우, 좌측에서는 1개의 빌딩, 우측에서는 2개의 빌딩이 보이는 경우의 수

 

city[1][1][1] 를 통한 city[2][2][1], city[2][1][2] 값 계산 예시

  

  위와 같은 방법을 통해 city[1][1][1]의 값으로 city[2][2][1], city[2][1][2] 의 값을 구할 수 있다. n의 값을 하나 더 늘린다는건, 위처럼 기존 city[n][l][r] 의 상태에서 모두 1층씩 더한 후 , 1층짜리 건물의 새로운 배치를 통해 city[n + 1][l][r]의 경우의 수를 구한다고 생각을 하면 된다.

 

  위의 경우에는 city[1][1][1] 로부터 다음으로 두 경우의 수만 확인이 가능하다. 하지만 아래와 같은 경우가 일반적인 경우이며, 참고할 수 있는 city의 관계가 세 경우가 존재한다.

 

 

• [1] : city[6][2][3] 의 값을 판단하기 위해서 city[5][2][2] 의 값을 사용하였다. 그냥 맨 우측에 1층 빌딩 하나 추가하는 경우가 되므로 city[6][2][3] == city[5][2][2] + (...) 가 된다.
• [2] : city[6][3][2] 의 값을 판단하기 위해서 city[5][2][2] 의 값을 사용하였다. 그냥 맨 좌측에 1층 빌딩 하나 추가하는 경우가 되므로 city[6][3][2] == city[5][2][2] + (...) 가 된다.
• [3] : city[6][2][2] 의 값을 판단하기 위해서 city[5][2][2] 의 값을 사용하였다. 1층 빌딩은 기존 city[5][2][2]에서 맨 좌측 빌딩과 맨 우측 빌딩 사이 공간에 넣으면 좌측에서든 우측에서든 안 보이므로, 위 case 에선 총 4군데에 넣을 수 있다. 즉, city[6][2][2] == city[5][2][2] * 4 + (...) 가 된다. 곱해진 4는, 저 공간들 중 4개의 공간에 들어갈 수 있으므로 4를 곱하였다. 이는 n - 2 값에 해당이 된다.

 

  위 경우처럼, 임의의 city[n][l][r] 의 값을 구할 땐 n - 1 개의 빌딩을 가지는 case의 값들 중 세 가지 값을 확인하면 된다. 

 

  위 예시는 임의의 city[n][l][r] 값을 통해, n + 1 개의 빌딩을 가지는 세 가지 경우에 참고되는 상황을 보인 것 이고, 이를 통해 임의의 city[n][l][r]의 값을 판단할 때 위 과정을 역으로 생각하여 n - 1 개의 빌딩을 가지는 세 가지 경우를 파악하여 값을 정의할 수 있다.

 

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

 

  이 식을 통해 city[1][1][1] 부터, 구하고자 하는 city[N][L][R] 의 값을 구할 수 있다. 3차원 array를 사용하므로 3중 for문을 사용하면 된다. N, L, R 의 최대 크기는 100 이므로 3중 for문으로 구현을 하여도 최대 실행 횟수는 100^3 == 백만번 이므로 실행 시간에 큰 무리가 가지 않는다.

---

 Code 

#include <iostream>
#include <vector>
#define p 1000000007
 
using namespace std;
 
int N;
int L, R;
 
unsigned long long city[101][101][101]; // max(N) == 100        max(L) == 100        max(R) == 100
 
int main() {
    cin >> N;
    cin >> L >> R;
 
    city[1][1][1] = 1;
 
    for (int n = 2; n <= N; n++) 
        for (int l = 1; l <= L; l++)
            for (int r = 1; r <= R; r++)
                city[n][l][r] = (city[n - 1][l][r - 1] + city[n - 1][l - 1][r] + city[n - 1][l][r] * (n - 2)) % p;
 
    cout << city[N][L][R];
}

---

 고찰 

  처음에는 경우의 수가 발생할 수 있는 케이스들을 나누어 판단을 하며 문제를 풀어갔는데, 결국 이 방법을 통해서는 풀지 못했다. N의 값이 100인 경우 총 100팩토리얼의 경우의 수가 있으므로, 좀 골치였다.

 

  초기 값부터 시작해서 차츰차츰 이전 값들을 참고하여 값이 구해진 영역을 키워나가며 값을 구해가는 Dynamic programming 알고리즘은 상당히 유용하고 많이 쓰인다. 초기값부터 시작을 하여 그로부터 계속해서 다음 값을 파생시키며 각 값들의 관계와 규칙을 파악한 후 이 문제의 점화식을 찾아내는 것, 이 요점을 제대로 숙지하고 있어야 할 것 같다.