[BaekJoon] 8895 막대 배치 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();

    static int n, l, r;
    static long[][][] dp;

    static void input() {
        n = scanner.nextInt();
        l = scanner.nextInt();
        r = scanner.nextInt();

        // dp[stickNum][left][right] = stickNum개의 막대로 왼쪽에서는 left개, 오른쪽에서는 right개의 막대가 보이도록 배치하는 경우의 수
        dp = new long[n + 1][n + 1][n + 1];
    }

    static void solution() {
        // stickNum개의 막대들 중 가장 길이가 짧은 막대를 특정 위치에 놓는다고 생각했을 때, 아래와 같은 점화식이 나올 수 있다
        // 1. 가장 짧은 막대를 가장 왼쪽에 놓는 경우
        //  - 가장 왼쪽에 짧은 막대를 놓으면 왼쪽에서 볼 때 막대의 개수가 하나 증가한다
        //  - 그러므로 dp[stickNum - 1][left - 1][right]개의 경우의 수가 만들어진다
        // 2. 가장 짧은 막대를 가장 오른쪽에 놓는 경우
        //  - 가장 오른에 짧은 막대를 놓으면 오른쪽에서 볼 때 막대의 개수가 하나 증가한다
        //  - 그러므로 dp[stickNum - 1][left][right - 1]개의 경우의 수가 만들어진다
        // 3. 가장 짧은 막대를 위 두 경우가 아닌 곳에 놓는 경우
        //  - 중간에 짧은 막대를 놓으면 왼쪽이나 오른쪽에서 볼 때 다른 막대들이 가려 막대의 개수가 증가하지 않는다
        //  - 그러므로 dp[stickNum - 1][left][right] * (stickNum - 2)개의 경우의 수가 만들어진다
        //  - 여기서 stickNum - 2는 가장 짧은 막대를 세울 수 있는 곳의 개수를 의미한다
        //      - 가장 왼쪽과 가장 오른쪽을 제외한 모든 곳에 세울 수 있기 때문에 두 곳을 제외한 stickNum - 2개의 위치에 세울 수 있다
        // 즉, dp[stickNum][left][right] = dp[stickNum - 1][left - 1][right] + dp[stickNum - 1][left][right - 1] + (dp[stickNum - 1][left][right] * (stickNum - 2))
        dp[1][1][1] = 1;

        for(int stickNum = 2; stickNum <= n; stickNum++) {
            for(int left = 1; left <= stickNum; left++) {
                for(int right = 1; right <= stickNum; right++) {
                    dp[stickNum][left][right] = dp[stickNum - 1][left - 1][right] + dp[stickNum - 1][left][right - 1]
                            + (dp[stickNum - 1][left][right] * (stickNum - 2));
                }
            }
        }

        sb.append(dp[n][l][r]).append('\n');
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        while(T-- > 0) {
            input();
            solution();
        }
        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            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());
         }
    }
}