https://www.acmicpc.net/problem/15902
문제 요약
- 자르는 연산, 합치는 연산으로 A배열을 B로 만들때
- 최소 연산 횟수, 경우의 수 구하기(연산의 순서가 다름)
접근법
- A배열의 가장 끝 원소(왼쪽이나 오른쪽)를 봤을때....오른쪽에서부터 본다고 하자
- B와 같다 => 넘어가면됨. 굳이 건드릴 필요가 없음
- 다르다 : 두 가지 경우가 있음
- (2, 1) ==> 잘라야함
- (1, 2) ==> 합치긴 합쳐야하하는데, A의 다음 원소를 봐야함
- 다음 원소가 1 : 그냥 합치면 됨
- 다음 원소가 2 : 2를 잘라야함
- 일단 이렇게 하면 꼭 해야할 일만 하기때문에 최소 횟수는 보장할 수 있을 것임
- 자르지 않거나, 합치지 않고서는 딱히 배열을 맞출 방법이 없기때문에
- 경우의 수를 구하기에 앞서 연산간의 순서가 있는 경우가 있고, 독립된 그룹을 이루는 경우가 있음
- 독립된 그룹 : 쭉 살펴보다가 B와 같아지는 순간은 어쨌든 작업이 끝나고 새로운 작업이 생김
- 연산간의 순서
- 자를때 => 그냥 주어진 원소를 자르면 됨
- 합칠때 => 그냥 합칠수 없고, 어디선가 자르는 연산이 있는 후에 합치는 경우가 발생함
- 1 2 1
- 2 2
- 관찰해보면 자름 -> 합침으로 우선순위가 생기고
- 자름이 최대 두개의 합침에 영향을 주고, 합침은 최대 두개의 자름으로부터 영향을 받음
- 자름과 합침의 개수가 같거나 한쪽이 1만큼만 크는 경우만 발생함
- 더 커지면 별도의 그룹으로 분리가 됨
- 독립은 각각을 combination으로 해결할 수 있음
- n개 중에서 독립할 그룹만큼 자리를 확보하는 경우의 수
- 독립한 그룹내에서는 알아서 경우의 수를 적용할 것이고..
- 연쇄적으로 combination을 구하면 독립한 그룹들에 대한 경우의 수는 구함
- 독립이 발생하는 경우
- 원소가 같을때
- 합침을 할때 뒤에 원를 자를 필요가 없을때
- 독립한 그룹 내부의 경우의 수는 자름-합침의 개수에 따라 적절한 경우의 수가 있을 것임
- dp [자름횟수][합침횟수] : 그런데 더 생각해보면 합침횟수만큼 필요하지는 않고 같거나/다르거나로 해서 [자름횟수][2]로 줄일 수 있음
- 구하는 방법을 dp 연쇄반응으로 구했는데 요약해보면
- 자름 a, 합침 b 인 상태에서 자름이 하나 생기는 경우와 합침이 하나 생기는 경우가 있을 것임
- 추가 되는 것이 기존에 마지막으로 추가된 원소에 대해 발생한다고 치면
- 자르는 경우 : 마지막으로 추가된 원소보다 앞 순서에 위치하면됨
- 합치는 경우 : 마지막으로 추가된 원소보다 뒷 순서에 위치하면 됨
- 필요한 값 : 마지막으로 추가된 원소의 순서 당 경우의 수
- 구할 값 : 새로 추가된 원소의 순서 당 경우의 수
- 구하는 방법 : 마지막으로 추가되는 원소의 범위에 대해 +, - 방법을 이용해서 구간 업데이트 후 나중에 누적합을 구함
- 더 생각해보면 자름 < 합침인 경우는 합침 > 자름인 경우의 수와 동일함(서로 교환해서 적용하는 모습임)
- 독립이 발생할때마다 자름/합침이 몇번 발생했는지를 카운팅해서 어딘가에 저장해놓고,
- 나중에 저장해놓은 값을 계산해가면서 독립 * 독립한 그룹내의 경우의 수를 곱해나감
newbieski