[C++] BAEKJOON 8895번 막대배치(ACM-ICPC Daejeon 2012)

문제보러가기

8895번: 막대 배치

동적계획법을 사용한 문제였습니다. 먼저 점화식을 세워보도록 하겠습니다.

dp[n][l][r] 를 n 개의 막대에 대해, 왼쪽에서 보이는 막대가 l 개, 오른쪽에서 보이는 막대가 r 개인 경우의 개수 라고 정의하겠습니다. 그리고 이를 하위 문제로 나누기 위해서 l 과 r 값에 영향을 많이 주는 길이 n 막대가 아닌 길이 1 막대로 생각을 해보겠습니다.

• 길이 1 막대가 가장 왼쪽에 위치한 경우

  이 막대가 영향을 줄 수 있는 건 n 과 l 입니다. 이 막대가 사라진다면 n과 l 만 1 감소하게 되죠. 따라서 다음과 같이 표현 할 수 있습니다.

  dp[n-1][l-1][r]

• 길이 1 막대가 가장 오른쪽에 위치한 경우

  위와 유사하게 n 과 r 에만 영향을 미치고, 다음과 같이 표현됩니다.

  dp[n-1][l][r-1]

• 길이 1 막대가 2~n-1 에 위치한 경우

  길이 1인 막대가 2~n-1 에 위치한다면 사라지더라도 l 과 r 값에 영향을 주지 않습니다. 따라서 n 만 1 줄어들겠죠.

  dp[n-1][l][r-1]

 

이 때 1,2 번째 case 는 1가지 경우, 3번째 case는 n-2 가지 경우가 있으므로, 다음과 같은 점화식을 얻을 수 있습니다.

dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1]  + (n-2) * dp[n-1][l][r]

 

전체 풀이

이 점화식만 구했다면 문제 푸는 건 어렵지 않습니다.

#include <iostream>

using namespace std;

long long dp[21][21][21];

int main(int argc, const char * argv[]) {
    
    dp[1][1][1] = 1;
    for (int n=2;n<=20;n++){
        for (int l=1;l<=20;l++){
            for (int r=1;r<=20;r++){
                dp[n][l][r] = dp[n-1][l-1][r] + dp[n-1][l][r-1] + (n-2)*dp[n-1][l][r];
            }
        }
    }
    
    int T;
    cin >> T;
    for (int t=0;t<T;t++){
        int n,l,r;
        cin >> n >> l >> r;
        cout << dp[n][l][r] << endl;
    }
    return 0;
}