백준 1146 <지그재그 서기> Python

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

---

브루트 포스나 BFS 의 식으로도 풀 수 있지만 시간제한에 걸리게 됩니다.

다른 방법을 찾아봅시다.

 

우리는 N 명의 학생을 줄세워야 합니다.

그 중 번호가 가장 큰 N 번째 학생을 P 번째 순서에 줄 세우는 경우를 생각해보겠습니다.

그럼 남은 N-1 명의 학생을 줄 세워야 하는데, 어차피 수의 대소만이 중요하기 때문에 지그재그 패턴만 맞으면 어떤 학생이 어디에 서던 중요하지 않습니다.

즉 N 번째 학생을 P 번째 세우고 양 옆에 남은 학생들을 다시 줄세우는 작은 단계로 쪼갤 수 있습니다.

즉 이 문제를 DP 로 풀 수 있습니다.

 

N 명의 학생 중 P 번째 자리에 N 번째 학생을 줄세운다고 생각하겠습니다.

해당 경우를 A_NP 라고 부르겠습니다.

 

P 가 1 인 경우 == N 번째 학생이 첫 번째 자리에 서 있을 경우

남아있는 번호는 모두 N 보다 작으므로 지그재그 패턴은

N - (작은수 - 큰수 - 작은수 - ... ) 의 패턴을 띄게 됩니다.

즉 경우의 수는 N-1 명의 학생을 지그재그로 줄세우는 경우의 수와 같습니다.

N-1 명의 학생을 지그재그로 줄세우는 경우의 수는 N-1 번 학생을 모든 자리에 세워본 경우의 수의 합과 같으므로

A_N1 = ∑(P = 1~N) (A_(N-1)(P)) 입니다.

 

P 가 2 인 경우 == N 번째 학생이 두 번째 자리에 서 있을 경우

역시 남아있는 번호는 모두 N 보다 작으므로 지그재그 패턴은

(작은수) - N - (작은수 - 큰수 - ...) 의 패턴을 띄게 됩니다.

즉 경우의 수는 N-1 명의 학생 중 왼쪽에 설 한명을 정하는 경우의 수에

N-2 명의 학생을 지그재그로 줄세우는 경우의 수를 곱한 값과 같습니다.

A_N2 = (N-1)_C_(1) * ∑(P = 1~(N-2)) (A_(N-2)(P))

 

...

 

P 가 K 인 경우 == N 번째 학생이 K 번째 자리에 서 있을 경우

(... - 작은수) - N - (작은수 - ...) 의 패턴을 띄게 됩니다.

즉 경우의 수는 N-1 명의 학생 중 왼쪽에 설 K-1 명을 정하는 경우의 수에

K-1 명을 지그재그로 줄 세우는 경우의 수

N-K 명을 지그재그로 줄 세우는 경우의 수를 곱한 값과 같습니다.

A_NK = (N-1)_C_(K-1) * ∑(P = 1~(K-1)) (A_(K-1)(P)) * ∑(P = 1~(N-K)) (A_(N-K)(P))

 

코드로 써보자면

memo[N][P] = N 명의 학생중 P 번째 자리에 N 번째 학생을 위치시킬 때 경우의 수

memo[N][P] = (N-1)_C_(P-1) * sum(memo[P-1]) * sum(memo[N-P]) 가 됩니다.

 

하지만 고려할 경우가 더 있습니다.

일반적으로 양 끝의 수열은 지그재그의 형태가 정해져 있지 않습니다.

즉 큰수 - 작은수 - 큰수 - ... 일수도 있고 작은수 - 큰수 - 작은수 - ... 일 수도 있습니다.

하지만 가장 큰 수를 고정시키는 방식이었기 때문에 양쪽에 오는 수열은 형태가 고정됩니다.

즉 전체 지그재그 수열을 2 로 나눈 뒤 계산해야 합니다.

 

다만 P == 1 / P == 2 / P == N-1 / P == N 일 경우

한쪽 수열에 속해있는 숫자의 수가 0 / 1 이므로 수열의 형태는 하나밖에 없습니다.

즉 이 경우에는 해당하는 쪽의 수열은 2로 나누어주지 않아도 됩니다.

물론 양쪽 다 해당할 경우 양쪽 모두 나누어주지 않습니다.

---

import sys

input = sys.stdin.readline

def solution(N):

    # DP / memo[N][P] = A_NP = N 명중 P 번째에 N 번째 학생이 있을 경우

    memo = [[0 for _ in range(N+1)] for __ in range(N+1)]

    memo[0][0] = 1

    memo[1][1] = 1

    # 순회하면서 채우기

    for n in range(2, N+1):

        for p in range(1, n+1):

            # (n-1)_C_(p-1)

            comb = 1

            for num in range(p-1):

                comb *= n-1-num

            for num in range(1, p):

                comb //= num

            # p == 1 / 2 / n-1 / n 일때

            if p <= 2 or p >= n-1:

                # 둘 다 일때

                if p <= 2 and p >= n-1:

                    # 둘 다 나눠주지 않음

                    # 어차피 수열의 형태가 한가지씩 뿐

                    memo[n][p] = (sum(memo[p-1]) * sum(memo[n-p])) * comb

                # 둘 중 하나일때

                else:

                    # 둘 중 하나만 나눠줌

                    # 둘 중 하나만 수열의 형태가 큰-작 / 작-큰 으로 두배

                    memo[n][p] = (sum(memo[p-1]) * sum(memo[n-p])) // 2 * comb

            # 둘 다 아닐때

            else:

                # 둘 다 나눠줌

                memo[n][p] = (sum(memo[p-1]) * sum(memo[n-p])) // 4 * comb

    return sum(memo[-1]) % 1000000

# 입력

N = int(input().strip())

print(solution(N))