BOJ 8895 막대 배치(Java)

문제 탐색하기

• 높이가 1, 2, …, n인 막대 n개가 일렬로 배치되어 있다.
• 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다.
• 문제의 첫번째 예시 같은 경우, 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다.

코드 설계하기

구현 방법

막대가 가질 수 있는 경우의 수를 코드로 표현하려면?

• 가질 수 있는 배치의 경우의 수를 x라 하고 i를 현재 막대의 총 개수, j가 왼쪽에서 봤을때, k를 왼쪽에서 봤을때 라고 가정하면…

arr[i][j][k] = x

위와 같은 형식으로 표현할 수 있을 것이다.

점화식

dp[i][j][k] += dp[i - 1][j - 1][k] // 왼쪽에 하나 더 놓는 경우
            + dp[i - 1][j][k - 1]  // 오른쪽에 하나 더 놓는 경우
            + (dp[i - 1][j][k] * (i - 2)); 
		    // 그 외 위치에 골라 넣는 경우는 
		    // 왼/오 에서 보는 가짓수는 동일하고, 
		    // 가장자리 개수를 제외한 i - 2개만큼 

시간 복잡도

• 계산할때 3중 for문이 들어가지만, n, l, r 각각의 값 자체는 그렇게 크지 않다. (1 ≤ l, r ≤ n ≤ 20)
  • 계산 시 시간 복잡도는 O(19 * 20 * 20) = O(7600) 으로 크지 않아 상수 시간 내 충분히 연산이 가능하다.
• 정답 입출력은 저장된 배열 값에 대한 접근만 일어나므로 O(1)

정답 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    private static int N, l, r;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(st.nextToken());

        long[][][] dp = new long[21][21][21];

        // 첫번째 값은 한개의 블록을 보는 경우의 수이다.
        dp[1][1][1] = 1;

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


        while (t-- != 0) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            l = Integer.parseInt(st.nextToken());
            r = Integer.parseInt(st.nextToken());

            bw.write(dp[N][l][r] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();

    }
}