[BOJ] 백준 1328 고층빌딩

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

 Input 
3 2 2

 Output 

2 

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

N개의 빌딩을 재배열하는 경우의 수는 O(N!)이며,

좌우에서 보여지는 빌딩의 개수를 구한다면 O(N × N!)으로 TLE 발생.

 

DP[i][L][R] = i 번째 빌딩을 배치할 때, 왼쪽에서 보이는 빌딩 수 L / 오른쪽에서 보이는 빌딩 수 R

- 빌딩이 한개 놓여져 있는 경우) DP[1][1][1] = 1

- 빌딩이 두개 놓여져 있는 경우) DP[1][2][1] = DP[1][1][2] = 1

 

빌딩이 높은 빌딩부터 놓여져 있고, 마지막 높이 = 1인 빌딩을 놓는다고 가정해보자. (N → 1)

① 가장 왼쪽에 놓는 경우(1가지): DP[N-1][L-1][R]

    높이 1인 건물을 N-1개의 건물들 왼쪽에 추가한다면 왼쪽에서 보는 건물의 수가 증가

② 가장 오른쪽에 놓는 경우(1가지): DP[N-1][L][R-1]

③ 중간 어딘가에 놓는 경우(N-2가지): DP[N-1][R][L]*(N-2)

    높이가 1인 건물을 중간 어디에 놓아도 좌우에 보여지는 건물의 수는 변화가 없습니다.

    즉, dp[N-1][L][R]에서는 가장 양 옆을 제외한 N-2 경우의 수가 존재.

▶ DPN][L][R] =  DP[N-1][L-1][R] + DP[N-1][L][R-1] + DP[N-1][R][L]*(N-2)

→ 시간복잡도 O(N3)

 

시뮬레이션

예를 들어, 4개의 건물{1, 2, 3, 4}이 존재하며

{2, 3, 4}가 놓여져 있고 마지막 {1}을 놓는 경우입니다.

            L  R

2 3 4    3  1

3 2 4    2  1

2 4 3    2  2

3 4 2    2  2

4 2 3    1  2

4 3 2    1  3

 

(1). 가장 왼쪽에 추가 → L + 1

              L  R

1 2 3 4    4  1

1 3 2 4    3  1

1 2 4 3    3  2

1 3 4 2    3  2

1 4 2 3    2  2

1 4 3 2    2  3

 

(2). 가장 오른쪽에 추가 → R + 1

              L  R

2 3 4 1    3  2

3 2 4 1    2  2

2 4 3 1    2  3

3 4 2 1    2  3

4 2 3 1    1  3

4 3 2 1    1  4

 

3. 양 끝을 제외한 중간에 추가

               L  R                    L  R

2 1 3 4    3  1   |  2 3 1 4    3  1

3 1 2 4    2  1   |  3 2 1 4    2  1

3 1 2 4    2  1   |  3 2 1 4    2  1

3 1 4 2    2  2   |  3 4 1 2    2  2

4 1 2 3    1  2   |  4 2 1 3    1  2

4 1 3 2    1  3   |  4 3 1 2    1  3

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static final int MOD = 1000000007;
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new   InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
         
        long[][][] DP = new long[101][101][101];
        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][k]*(i-2); 
                    DP[i][j][k] += DP[i-1][j-1][k]; 
                    DP[i][j][k] += DP[i-1][j][k-1]; 
                    DP[i][j][k] %= MOD;
                }
            }
        }
         
        // 정답출력
        System.out.println(DP[N][L][R]);
    }
}