[BOJ] 15902번: Split and Merge

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

일단 경우의 수는 나중에 생각하고, 최소의 연산이 몇 회일지 고민을 해봅시다. 문제의 그림에서 위에는 작대기가 그어져있는데 아래에는 그어져있지 않거나, 반대로 위에는 작대기가 안그어져있는데 아래에는 그어져있으면 추가적인 연산이 필요함을 알 수 있습니다. 이를 통해 최소 연산의 횟수는 구할 수 있는데, 그 다음에 방법이 몇 가지인가가 문제입니다. 잘 생각해보면 작대기가 딱 맞아떨어지는 지점들로 경우의 수가 분리될 수 있고, 각 분리된 곳에서 작대기의 갯수를 N개라고 하면, 형태는 반드시

1 2 2 2 2

2 2 2 2 1

or

1 2 2 2 1

2 2 2 2

임을 알 수 있습니다.

이 때 먼저 Split이 이루어져야 Merge가 가능하므로 각 Split 지점들을 제일 먼저 처리하고 나면 결론적으로 $D_i = \sigma_{0 <= j < i-1} D_jD_{i-1-j}(i-1)!/j!(i-1-j)!$이 됩니다. 이 병렬적인 chunk들에 대해 다시 한 번 중복순열의 경우의 수를 곱해주면 됩니다.

https://github.com/blisstoner/BOJ/blob/master/15902.cpp