지그재그 서기( BOJ 1146 )

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

1146번: 지그재그 서기

 

문제 파악하기

학생들을 특정 규칙에 맞춰 줄을 세우는 문제입니다. 여기서의 규칙은 학생들의 키가 커졌다, 작아졌다를 반복하게 만들어야 한다는 것입니다. 예를 들어 { 1 3 2 4 } 또는 { 4 2 3 1 }과 같이 학생이 커졌다가 작아졌다가를 반복하게 줄을 서야하며, { 1 2 3 4 } 혹은 { 3 4 2 1 }과 같이 계속 작아지거나 커지는 경우가 있으면 안됩니다. 이렇게 줄을 세우는 경우의 수를 구하기 위해서는 어떤 방법이 있을까요?

 

문제 해결하기

우선, 문제를 추상화할 필요가 있습니다. 문제에서 원하는 건 (큰 수-작은 수) 혹은 (작은 수-큰 수) 순서로 줄을 세우는 것입니다. 그럼 우리는 현재 숫자보다 큰 수는 몇 개가 남았는지, 현재 숫자보다 작은 수는 몇 개가 남았는지 알고 있어야 합니다. 그래야 큰 숫자 중에서 하나를 고르거나 작은 숫자 중에서 하나를 고를 수 있기 때문입니다. 다만, 해당 숫자가 어떤 것인지는 알 필요가 없습니다. 우리는 나올 수 있는 모든 경우의 수를 구하는 것이지, 각각의 경우를 출력하지 않기 때문입니다. 지금까지의 내용을 정리하면, 다음과 같이 재귀함수를 설계할 수 있다.

>> int sv( int idx, int l, int r, int s );

 

sv( ) 함수에서 idx는 현재 줄에 서있는 학생을 의미하며, l은 현재 숫자보다 작은 숫자, r은 현재 숫자보다 큰 숫자의 개수를 의미합니다. 마지막으로 s는 현재 큰 수를 뽑아야 하는지, 작은 수를 뽑아야 하는지 확인하는 역할입니다. 이 상황에서 우리가 갈 수 있는 다음 상태는 여러 가지 있습니다. 우선, s의 방향에 따라 오른쪽 혹은 왼쪽으로 이동할 것이며, 이동할 때에는 몇 번째 숫자를 선택했는냐에 따라 l값과 r값이 변할 수 있습니다.

 

예를 들어 sv( 2, 2, 1, 0 )의 경우, 지금 숫자보다 작은 숫자(s=0)를 골라야 하며, 이 때 나올 수 있는 경우의 수는 총 2가지 입니다. 왼쪽에 있는 숫자 중 가장 큰 숫자로 이동해서 sv( 3, 1, 1, 1 )로 되는 경우와 가장 작은 숫자로 이동해서 sv( 3, 0, 2, 1 )로 되는 경우입니다. 첫 번째 경우에는 왼쪽에서 가장 큰 숫자로 이동했기에 오른쪽에는 여전히 1개의 숫자가 남아있으며, 왼쪽에는 가장 작은 숫자 1개가 남아있어 sv( 3, 1, 1, 1 )로 됩니다. 하지만, 왼쪽의 가장 작은 숫자를 선택한다면 해당 숫자의 왼쪽에는 아무 숫자도 남아있지 않으며, 오른쪽에는 기존의 숫자 1개와 왼쪽에 남아있는 숫자 중 현재 선택한 숫자보다 큰 숫자 1개가 남아있게 되어 sv( 3, 0, 2, 1 )로 됩니다.

 

이렇게 직접 숫자를 저장하지 않고, 개수를 사용하더라도 효율적으로 다음 상태를 구할 수 있으며, 이를 통해 소스코드를 설계할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#define NMAX 105
#define MOD 1000000
 
int N;
int dp[NMAX][NMAX][NMAX][2];
 
long long int ret;
 
// l: 왼쪽에 남아있는 수 / r: 오른쪽에 남아있는 수 / s: 현재 골라야하는 방향
int sv(int idx, int l, int r, int s) {
    // 메모이제이션
    if(dp[idx][l][r][s] >= 0) return dp[idx][l][r][s];
 
    // 종료조건
    if(idx == N) {
        if(!l and !r) return dp[idx][l][r][s] = 1;
        else return dp[idx][l][r][s] = 0;
    }
    else {
        long long int ret=0;
 
        // 작은 수 고르는 단계
        if(s == 0) {
            for(int i=l-1;i>=0;i--) {
                ret = ( ret+sv(idx+1, i, r+(l-i-1), 1) )%MOD;
            }
        }
 
        // 큰 수 고르는 단계
        else {
            for(int i=r-1;i>=0;i--) {
                ret = ( ret+sv(idx+1, l+(r-i-1), i, 0) )%MOD;
            }
        }
 
        return dp[idx][l][r][s] = ret;
    }
}
 
int main() {
    // input
    scanf("%d", &N);
    
    if(N == 1) printf("1");
    else {
        // dp
        memset(dp, -1, sizeof(dp));
        for (int i=1;i<=N;i++) {
            for (int s=0;s<2;s++) {
                ret = ( ret+sv(1, i - 1, N - i, s) )%MOD;
            }
        }
        
        // print
        printf("%lld", ret);
    }
}

후기

점화식을 쉽사리 도출하기 어려웠던 문제였습니다.