2025/02/06 백준 8895 막대 배치

난이도: P5

알고리즘: dp

 

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

 

1. 문제 탐색

 

제한 시간: 1초, 메모리 제한: 256MB

 

완전탐색으로 풀기엔 시간이 너무 많이 걸릴 것 같았다. 1~n 길이의 n개 막대를 배치하려면 n!의 경우의 수가 발생하고 개수를 셀 때에도 추가적으로 필요하기 때문이다.

 

dp로 이전 것을 활용해서 풀어야 시간이 절약된다고 생각했다. n개의 막대를 배치할 때 1~n-1길이의 막대를 배치하고 n길이의 막대를 위치시키려고 생각했으나 너무 복잡해서 해결할 방법이 생각이 나지 않았다. 해설지를 참고하니, 2~n길이의 막대를 배치하고 길이가 1인 막대를 위치시키는 게 더 문제가 단순해진다고 했다.  

 

2. 코드 설계하기

 

dp[n][l][r] : n개의 막대가 있을 때 왼쪽에서 보이는 개수가 l이고 오른쪽에서 보이는 개수가 r인 경우의 수

//크기가 2~n인 n-1개의 막대가 배열되어있고, 길이가 1인 막대를 위치시킨다고 했을 때
//n개의 막대&왼쪽에서 보이는 막대의 개수가 l개&오른쪽에서 보이는 막대의 개수가 r개 
//= n-1개의 막대&왼쪽에서 보이는 막대의 개수가 l-1개&오른쪽에서 보이는 막대의 개수가 r개     (길이가 1인 막대를 맨 왼쪽에 위치)
// +n-1개의 막대&왼쪽에서 보이는 막대의 개수가 l개&오른쪽에서 보이는 막대의 개수가 r-1개     (길이가 1인 막대를 맨 오른쪽에 위치)
// +n-1개의 막대&왼쪽에서 보이는 막대의 개수가 l개&오른쪽에서 보이는 막대의 개수가 r개*(n-2) (길이가 1인 막대를 양끝이 아닌 그 사이에 위치)
dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-2);

 

3. 시도회차별 수정 사항

 

해설지 참고하여 코드 작성하였습니다.

 

4. 정답코드

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, l, r, t;

    vector<vector<vector<long long>>> dp(21, vector<vector<long long>>(21, vector<long long>(21, 0)));

    //dp[n][l][r] : n개 막대, 왼쪽에서 보이는 막대 개수 l개, 오른쪽에서 보이는 막대 개수 r개
    dp[1][1][1] = 1;

    for(int n=2; n<=20; n++)
    {
        for(int l=1; l<=n; l++)
        {
            for(int r=1; r<=n; r++)
            {
                //크기가 2~n인 n-1개의 막대가 배열되어있고, 길이가 1인 막대를 위치시킨다고 했을 때
                //n개의 막대&왼쪽에서 보이는 막대의 개수가 l개&오른쪽에서 보이는 막대의 개수가 r개 
                //= n-1개의 막대&왼쪽에서 보이는 막대의 개수가 l-1개&오른쪽에서 보이는 막대의 개수가 r개     (길이가 1인 막대를 맨 왼쪽에 위치)
                // +n-1개의 막대&왼쪽에서 보이는 막대의 개수가 l개&오른쪽에서 보이는 막대의 개수가 r-1개     (길이가 1인 막대를 맨 오른쪽에 위치)
                // +n-1개의 막대&왼쪽에서 보이는 막대의 개수가 l개&오른쪽에서 보이는 막대의 개수가 r개*(n-2) (길이가 1인 막대를 양끝이 아닌 그 사이에 위치)
                dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + dp[n-1][l][r] * (n-2);
            }
        }
    }

    cin>>t;

    for(int i=0; i<t; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;

        cout<<dp[a][b][c]<<'\n';
    }
}