지그재그 순열(Alternating Permutaion) 의 개수 구하기

소개

Zigzag Permutaion, Alternating Permutaion이라고 불리는 순열은 다음과 같은 대소 관계를 지니도록 수를 나열한 것이다.

 

a부터 g까지의 수가 나열되어 있을 때

 

$a < b > c < d > e < f > g$

$a > b < c > d < e > f < g$

 

이 순열은 감소 - 증가 - 감소 - 증가... 하거나 증가 - 감소 - 증가 - 감소... 하는 패턴이 반복된다.

 

올라갔다 내려갔다 하는 모습이 마치 지그재그 모양을 연상시켜서 지그재그 순열이라고 부르는 것 같다.

자연수 n까지 지그재그 순열을 만드는 경우의 수 구하기

1부터 n까지 자연수를 나열한 수열이 지그재그 순열이 되는 경우의 수를 구하는 방법은 여러가지가 있지만 프로그래밍 대회 수준에서 신뢰할 수 있고 빠르게 계산할 수 있는 방법 두가지를 소개하겠다.

1. André's theorem

n까지 자연수가 있을 때 경우의 수를 $Z_{n}$이라고 하자.

 

다음 점화식을 동적계획법으로 계산한다. 카탈란 수와 비슷하게 생겼다.

 

$Z_{n} = 2A_{n}$

$A_{n} = \sum^{n - 1}_{k = 0}{n - 1 \choose k}A_{k}A_{n - 1 - k}$

2. Euler Zigzag Number (Entringer Number)

$Z_{n} = 2E(n, n)$ 여기서 E(n, n)은 Entringer Number라는 이름의 점화식이다.

 

m을 n 이하의 자연수라고 한다면

 

$E(n, k) = E(n, k - 1) + E(n - 1, n - k) \; (E(0, 0) = 1, E(m, 0) = 0)$

 

역시 동적계획법으로 풀어주면 된다.

참고

$n \geq 23$ 만 되어도 long long 범위를 초과한다.

관련 문제 풀기

지금까지 백준에서 확인된 것 중 두 문제가 지그재그 순열의 개수를 구하는 문제이다.

 

www.acmicpc.net/problem/1146 - 풀이

www.acmicpc.net/problem/3948 - 풀이