[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 10256번: Mutation  (0) 2018.07.28
[BOJ] 9537번: Magical GCD  (2) 2018.07.28
[BOJ] 1605번: 반복 부분문자열  (0) 2018.07.27
[BOJ] 15903번: 카드 합체 놀이  (0) 2018.07.27
[BOJ] 15894번: 수학은 체육과목 입니다  (0) 2018.07.27
[BOJ] 11505번: 구간 곱 구하기  (0) 2018.07.27
  Comments
댓글 쓰기