[BOJ] 백준 8895 막대배치

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

 Input 

4

4 1 2

4 1 1

5 2 4

20 2 1

 

 Output 

2

0

4

6402373705728000

▶ [BOJ] 1328 고층빌딩와 동일한 문제로 해당 풀이 참조

[BOJ] 백준 1328 고층빌딩

 

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

동적계획법(Dynamic Programming, DP)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    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());
         
        while(T-- > 0) {
            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(DP[N][L][R]);
        }
    }
}