문제 탐색하기

입력 자료 정리

1. n은 구하려는 막대의 길이, l은 왼쪽에서 보이는 막대의 개수, r은 오른쪽에서 보이는 막대의 개수다

해결 방법 추론

1. 해당 문제를 보면서 제일 먼저 떠올린 방법은 이전 막대의 개수에서 한개의 막대를 배치에 추가했을 때, 각 위치에서 보이는 막대의 수를 확인해서 가짓수를 갱신하는 것이다
2. 해당 방법은 완전탐색과 값을 누적하는 DP 방법으로 구현할 수 있다
3. 하지만 완전탐색의 경우, 20^(20x20)의 경우의 수가 발생하기 때문에 선택할 수 없다
4. 따라서 DP를 이용한다면 시간복잡도를 줄여서 해결할 수 있을 것이다
5. 정말 줄일 수 있는지 확인하기 위해, 점화식을 고민했다
6. 먼저 dp는 3가지 상태를 관리하고, 그때의 가짓수를 값으로 관리한다
7. dp가 관리하는 3가지 상태는 막대의 개수, 왼쪽에서 보이는 막대개수, 오른쪽에서 보이는 막대개수다
8. 이어서 새로운 막대가 추가되었을 때를 고민했다
9. 보통 크기의 양 끝 값을 고민하면 되는데, 가장 큰 값을 추가할 경우 고민할 거리가 많아진다
10. 하지만 가장 작은 값을 추가할 경우, 양끝은 1개씩 보이는 개수가 증가하고 가운데는 아예 증가하지 않는다
11. 따라서 조금 편하게 생각할 수 있는 가장 작은 값을 추가하기로 결정했다
12. 그렇게 했을 때 다음과 같은 점화식이 나온다
    점화식: dp[i][j][k] += dp[i-1][j][k-1] + dp[i-1][j-1][k] + (dp[i-1][j][k]);
13. 하지만 이렇게 할 경우, 예제에서 제공한 출력과 맞지 않는다
14. 놓치고 있는 부분이 하나 있었는데, 중간에 추가할 때 한가지 경우만 존재하는 것이 아니고
    전체 막대의 개수에 따라 여러가지 경우가 나올 수 있다
15. 따라서 양끝에 놓을 때를 제외한 (n-2)만큼을 곱해줘야 한다
16. 다시 점화식을 세우면 다음과 같다
    점화식: dp[i][j][k] += dp[i-1][j][k-1] + dp[i-1][j-1][k] + (dp[i-1][j][k] x (i-2));
17. 이제 이 점화식을 가지고 원하는 입력을 출력하면 정답이 될 것이다!

시간복잡도 계산

1. 시간복잡도는 21^3이거나 테스트케이스에 따른다.
   따라서 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 먼저 dp는 long타입 3차원 배열로 관리한다
2. 정상적인 구현을 위해 최초값은 초기화해야한다. 따라서 dp[1][1][1]은 1로 초기화했다
3. 이어서 들어오는 테스트케이스값과 각 n,l,r값을 변수로 관리한다

구현 코드 설계

1. dp는 3중 포문을 돌며 점화식에 따라 값을 갱신한다
2. 막대가 1인 경우는 l과 r이 모두 1인 경우밖에 존재하지 않으므로 2부터 시작한다

출력값 설계

1. 테스트케이스마다 점화식을 인덱스로 하는 DP값을 출력하면 정답이 된다.

정답 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long[][][] dp = new long[21][21][21];
        dp[1][1][1] = 1;
        for (int i = 2; i < 21; i++) {
            for (int j = 1; j < 21; j++) {
                for (int k = 1; k < 21; k++) {
                    dp[i][j][k] += dp[i-1][j][k-1] + dp[i-1][j-1][k] + (dp[i-1][j][k]*(i-2));
                }
            }
        }

        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

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

        br.close();
        bw.close();
    }

}

문제 링크

8895번 - 막대 배치