홍준이의 친위대( BOJ 3948 )

문제 : https://www.acmicpc.net/problem/3948

3948번: 홍준이의 친위대

 

문제 파악하기

N개의 숫자를 규칙에 맞게 세우는 경우의 수를 구하는 문제입니다. 통칭 지그재그 수열이라고 불리는 이 수열의 가짓수를 세는 방법에는 여러가지가 있지만, 점화식을 사용하여 가짓수를 구하는 방법을 사용해보겠습니다.

 

문제 해결하기

홍준이가 원하는 방식으로 나열한 N개의 숫자는 두 번째 숫자의 크기에 따라 2가지 종류로 구분할 수 있습니다. 두 번째 숫자는 첫 번째 숫자보다 클 수도 있고, 작을 수도 있습니다. 앞으로 두 번째 숫자가 큰 경우, 즉 숫자들이 small > large > small과 같은 순서로 배치된 상황을 [ sw = 0 ]번 수열이라고 정의하겠습니다. 마찬가지로 두 번째 숫자가 작은 경우, 즉 숫자들이 large > small > large와 같은 순서로 배치된 상황을 [ sw = 1 ]번 수열이라고 정의하겠습니다. 우리는 2가지 종류의 수열을 활용해서 N개의 숫자를 조건에 맞게 나열하는 경우의 수를 구해보겠습니다.

 

N개의 숫자를 나열할 때, 가장 중요한 점은 바로 가장 큰 숫자인 N의 위치입니다. N은 항상 주변에 작은 숫자밖에 없습니다. 따라서, N의 위치에 따라 왼쪽 수열과 오른쪽 수열이 달라지며, 우리는 N의 위치를 바꿔가며 왼쪽과 오른쪽에 나열할 수 있는 경우의 수를 각각 찾아보면 전체 N개의 숫자를 나열할 수 있는 경우의 수를 찾을 수 있습니다.

 

[ 왼쪽 수열 ]   N   [ 오른쪽 수열 ]

( 수열의 기본 구조 )

 

그럼 N을 기준으로 왼쪽과 오른쪽에 배치할 수 있는 수열의 가짓수는 어떻게 구할 수 있을까요? 이는 왼쪽에 올 수 있는 수열 길이의 최솟값과 최댓값을 구해서 확인할 수 있습니다. 왼쪽에 올 수 있는 수열 길이의 최솟값은 0개, 즉 N이 가장 왼쪽에 위치한 경우입니다. 그럼 왼쪽에 올 수 있는 수열의 최댓값은 얼마일까요? 왼쪽에 올 수 있는 수열 길이의 최댓값은 (N-1)개이며, 이는 N이 가장 오른쪽에 위치한 경우를 의미합니다. 이렇게 최솟값과 최댓값을 구했다면 반복문을 사용하여 각각의 경우에 나올 수 있는 왼쪽 수열과 오른쪽 수열의 가짓수를 구하면 됩니다. 가짓수를 구할 때 중요한 점은 왼쪽과 오른쪽의 수열을 구할 때, 어떤 종류의 수열인지 파악해야 합니다. 즉 [ sw = 0 ]번 수열인지 [ sw = 1 ]번 수열인지 구분해야하며, 이는 N의 주변에는 항상 작은 숫자(small)가 배치된다는 특징을 활용할 수 있습니다. N은 가장 큰 숫자이기 때문에 N의 왼쪽과 오른쪽에는 항상 작은 숫자가 배치되며, 이를 활용하면 왼쪽과 오른쪽에 어떤 종류의 수열이 배치되는지 확인할 수 있습니다. 그리고 왼쪽 수열의 가짓수와 오른쪽 수열의 가짓수, 그리고 왼쪽 수열에 배치할 수 있는 숫자의 종류를 이항계수로 구하면 우리는 원하는 결괏값을 얻을 수 있습니다. 이를 점화식으로 표현하면 다음과 같습니다.

 

dp[idx][left] = dp[j][left]*dp[(idx-1)-j][right] + _(i-1)C_j (0<=j<idx)

 

left와 right는 각각 왼쪽과 오른쪽 수열의 모양을 의미합니다. dp[idx]의 경우, 왼쪽 수열의 모양이 그대로 자신의 모양이 되기에 left 값을 가지고 있습니다. 이렇게 1부터 20까지 모든 경우의 수를 구한다음, 쿼리를 처리해주면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#define NMAX 21
typedef long long int lint;
 
int T, N;
lint dp[NMAX][2];
lint nCr[NMAX][NMAX];
 
int main() {
    // init
    // 이항계수 계산
    for(int i=1;i<NMAX;i++) {
        for(int j=0;j<=i;j++) {
            if(j == 0) nCr[i][j] = 1;
            else if(j == i) nCr[i][j] = 1;
            else nCr[i][j] = nCr[i-1][j] + nCr[i-1][j-1];
        }
    }
    
    // 수열 값 계산
    // dp[idx][sw]: idx개의 숫자로 만들 수 있는 sw모양 줄의 개수
    // sw=0) small>large>small... / sw=1) large>small>large...
    for(int idx=0;idx<NMAX;idx++) {
        if(idx < 2) dp[idx][0] = dp[idx][1] = 1;
        else {
            for(int j=0;j<idx;j++) {
                // 왼쪽과 오른쪽에 필요한 수열 모양 찾기
                int left = 1-(j%2);
                int right = 1-((idx-1-j)%2);
                
                // i를 기준으로 왼쪽에 j개만큼, 오른쪽에 (idx-1-j)개만큼 배치하기
                dp[idx][left] += dp[j][left]*dp[(idx-1)-j][right]*nCr[idx-1][j];
                
            }
        }
    }
    
    // 입력 및 출력
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
 
        if(N == 1) printf("1\n");
        else printf("%lld\n", dp[N][0]+dp[N][1]);
    }
}
 

후기

단순히 비트마스킹을 활용했다가 메모리 초과가 나와서 당황했던 문제였습니다. 문제를 해결하기 위한 핵심요소를 파악하는데 힘들었던 문제라서 기억에 더 남을 듯 합니다. 위에서 소개했듯이 지그재그 수열을 만드는 방법은 여러가지가 있어 수학 관련 알고리즘으로 수업을 진행해도 좋을 듯 합니다.

 

참고

위키피디아에는 재귀함수를 사용하여 지그재그 수열을 계산하는 방법을 소개하고 있습니다.

https://en.wikipedia.org/wiki/Alternating_permutation#Andr%C3%A9's_theorem

Alternating permutation - Wikipedia