[BOJ] 8895. 막대 배치

[작성일]

• 2022-03-13

[분류]

• 누적합
• 조합
  
  
  

[문제링크]

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

[요구사항]

• 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만드는 배치의 개수를 구하는 프로그램을 작성하시오.
  
  

[풀이]

전혀 감이 안 잡혀서 다른 블로그를 참조하였다.
[참고] https://glanceyes.tistory.com/4

dp를 이용해서 풀이
풀이 : 막대 높이가 가장 높은 것부터 시작해서 높이 내림차순으로 막대를 배치한다고 가정함.
dp[n][l][r] = 막대를 n개 배치했고 왼쪽에서는 l개, 오른쪽에서는 r개의 막대가 보이도록 하는 배치 개수

마지막에는 n개의 막대 중에서 가장 높이 낮은 막대(A)를 어느 위치에 놓았을 것이다.

1) A를 가장 왼쪽에 놓는 경우
dp[n][l][r] += dp[n-1][l-1][r]

2) A를 가장 오른쪽에 놓는 경우
dp[n][l][r] += dp[n-1][l][r-1]

3) A를 막대 사이의 위치(중간)에 놓는 경우
dp[n][l][r] += dp[n-1][l][r] * (n-2)

풀이를 보면 굉장히 심플한데 dp적으로 생각하는게 정말 어려운 것 같다.

[코드]

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

class Main {
    static int T;
    static long[][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        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());

            dp = new long[n + 1][n + 1][n + 1];
            sb.append(getCase(n, l, r) + "\n");
        }
        System.out.println(sb);
    }

    public static long getCase(int n, int l, int r) {
        dp[1][1][1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                for (int k = 1; k <= i; k++) {
                    dp[i][j][k] = dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i - 1][j][k] * (i - 2);
                }
            }
        }

        return dp[n][l][r];
    }
}