백준 8895번 : 막대 배치 [Java]

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

문제 탐색하기

문제는 높이가 1, 2, 3 ... n인 막대 n개를 양쪽에서 봤을 때 각각 l, r에 해당하는 수만큼 막대가 보이는 경우의 수를 구하면 된다.

 

일단 예제부터 범상치않다. 막대 20개일 때 왼쪽에서 2개, 오른쪽에서 1개가 보이는 경우의 수는 아래와 같다.

6402373705728000 // 64경 2373조 7057억 2800만

 

몇 가지를 고려해보며 어떻게 이런 큰 수가 나올 수 있는 지 생각해보면 된다.

 

1. 가장 큰 막대(n)를 맨 앞에 두는 경우

n이 맨 앞에 있을 때, 왼쪽에서는 무조건 제일 긴 막대인 n만 보인다. 이 때 n을 제거하면 남은 n - 1개의 막대에서 (l - 1, r)을 만족하는 경우의 수를 구하는 문제와 같다.

dp[n - 1][l - 1][r]

2. 가장 큰 막대(n)를 맨 뒤에 두는 경우

n이 맨 뒤에 있을 때, 오른쪽에서는 무조건 제일 긴 막대인 n만 보인다. 이 때 n을 제거하면 남은 n - 1개의 막대에서 (l , r - 1)을 만족하는 경우의 수를 구하는 문제와 같다.

dp[n - 1][l][r - 1]

3. 가장 큰 막대(n)를 중간에 두는 경우

n의 앞뒤로 n - 1개의 막대가 분포된다. 가장 큰 막대는 보이는 개수에 영향을 주지 않고 n - 1개를 배치하는 방법과 같다. 이 때 n - 1개 막대를 배치하게 되면 총 n - 2개의 자리가 생기는데 여기에 n을 배치할 수 있게 되므로 n - 2를 곱해주어야 한다.

 

이에 따라서 dp[n][l][r] = dp[n - 1][l - 1][r] + dp[n - 1][l][r - 1] + (n - 2) * dp[n - 1][l][r] 이라는 점화식을 얻을 수 있다.

코드 설계하기

1. dp를 담을 3차원 배열을 설정한다. 숫자가 큰것을 감안하여 BigInteger를 통해 계산한다.

2. dp 배열을 초기화 한다 (BigInteger는 원시형이 아닌 클래스이기 때문에 배열에 담을 시 null 로 초기화 된다)

3. dp[1][1][1]를 1로 초기화 하고 점화식을 통해 계산한다.

4. 처리된 입력에 따른 dp 값을 가지고 출력한다.

 

풀이

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Main {
     static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
    
    static int TC;
    static BigInteger[][][] dp = new BigInteger[21][21][21];
    
    public static void main(String[] args) {
        FastReader fr = new FastReader();
        TC = fr.nextInt();
        StringBuilder sb = new StringBuilder();
            
        init();
        
        for (int i = 0; i < TC; i++) {
            int n = fr.nextInt();
            int l = fr.nextInt();
            int r = fr.nextInt();
            sb.append(dp[n][l][r] + "\n");
        }
        System.out.print(sb);
    }
    
    static void init() {
        for (int i = 0; i < 21; i++) {
            for (int j = 0; j < 21; j++) {
                Arrays.fill(dp[i][j], BigInteger.ZERO);
            }
        }
        
        dp[1][1][1] = BigInteger.ONE;
        
        for (int n = 2; n < 21; n++) {
            for (int l = 1; l < 21; l++) {
                for (int r = 1; r < 21; r++) {
                    dp[n][l][r] = dp[n][l][r].add(dp[n - 1][l - 1][r]).add(dp[n - 1][l][r - 1]).add(dp[n - 1][l][r].multiply(new BigInteger(String.valueOf(n - 2))));
                }
            }
        }
    }
}