[SWEA] 3993 Pole

출처: [SWEA] SW 문제해결 심화 - Counting & Probability

 Input 

4

4 1 2

4 1 1

5 2 4

20 2 1

 

 Output 

#1 2

#2 0

#3 4

#4 6402373705728000

 

Test Case 개수 / (N, L, R)이 주어집니다.

- 1~N까지의 높이를 가지는 막대가 일직선상에 존재합니다. (같은 높이 존재 X)

- 왼쪽에서 보여지는 막대 개수 L과 오른쪽에서 보여지는 막대 개수 R이라고 했을 때,

가능한 막대 순서의 경우의 수를 구하시오. (1 ≤ N ≤ 20)

ex) N=5, L=3, R=2일 때, 가능한 막대의 배치 중 하나는 {1 3 5 2 4} 입니다.

 

※ [BOJ] 1328 고층빌딩 

[BOJ] 백준 1328 고층빌딩

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new   InputStreamReader(System.in));
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
         
        for(int tc=1; tc<=T; tc++) {
            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[21][21][21];
            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]; 
                    }
                }
            }
         
            // 정답출력
            System.out.println("#" + tc + " " + DP[N][L][R]);
        }
    }
}