BOJ 1146 - 지그재그 서기

 

문제 링크

• https://www.acmicpc.net/problem/1146

 

문제 풀이

 

일단 수는 1부터 $N$까지 하나씩만 사용하면 된다. 일단 수열을 만드는 조건을 조금 단순화 시켜서 시각화 해보면,

3번째 수를 2번째 수보다 큰 수에서 골랐다면, 그 다음 4번째 수는 3번째 수보다 작은 수, 그 다음은 4번째 보다 큰 수 이런 식으로 지그 재그 모양으로 고르게 된다.

 

이런 식으로 지그재그 모양으로 고르게 된다. 여기서, 우린 dp로 경우의 수를 구해 줄 수 있다.

 

$N$개의 수가 있을 때, 우린 최초의 수 $a$를 선택해보자. 그 다음 수 $b$를 선택하면, 우린 $a \rightarrow b$로의 수열을 일단 만들 었고, $b$에서 $a$로의 역방향 ($a$에서 $b$로의 증감 반대) 으로 시작하는 경우의 수를 찾으면 된다.

 

이때, $a$를 제외한 수 $N-1$개의 수 중에, $b$에서 시작 하며, $a \rightarrow b$의 역방향으로 경우의 수를 찾으면 된다.

 

 

예를 들면, 수열의 첫 번째, 두번째 수가 2, 4일 때의 경우의 수를 구해보자.

나머지 수들은 1, 3 이 되고, 4보다 작은 수인 1, 3을 모두 탐색 했을 때의 경우의 수가 2->4로 시작되는 경우의 수다.

이때 이것은, 수가 1, 2 이 남고, 3에서 시작해서 왼쪽 방향으로 탐색하는 경우의 수와 같다.

 

즉, 우리는 이미 우리가 구해놓은 경우의 수를 가지고 새롭게 경우의 수를 구할 수 있다.

 

$dp[N][K][D]$ 를 수가 N개 있을 때, $K$번째 수에서 $D$방향 (큰 쪽, 작은 쪽) 으로 탐색 했을 때 순열을 만들 수 있는 경우의 수라고 해보자.

 

$$dp[i][j][0] = \sum_{k = 1}^{j-1} dp[i-1][k][1]\\dp[i][j][1] = \sum_{k = j+1}^{N} dp[i-1][k-1][0]$$

$$ dp[2][1][1] = 1,\quad dp[2][2][0] = 1$$

 

#include<bits/stdc++.h>

using namespace std;

const int MOD = 1'000'000;
int N, dp[202][202][2];

int main () {
    cin >> N;

    if (N == 1) {
        cout << 1;
        return 0;
    }

    dp[2][1][1] = 1;
    dp[2][2][0] = 1;

    for (int i=3;i<=N;i++) {
        for (int j=1;j<=i;j++) {
            for (int k=1;k<=i;k++) {
                if (j == k) continue;

                if (j < k) {
                    //dp[i][j][1]
                    dp[i][j][1] += dp[i-1][k-1][0];
                    dp[i][j][1] %= MOD;
                } else {
                    //dp[i][j][0]
                    dp[i][j][0] += dp[i-1][k][1];
                    dp[i][j][0] %= MOD;
                }
            }
        }
    }

    int ans = 0;

    for (int i=1;i<=N;i++) {
        ans += dp[N][i][0];
        ans += dp[N][i][1];
        ans %= MOD;
    }

    cout << ans;
}