https://www.acmicpc.net/problem/22880
요약
- 서로 다른 수의 수열이 주어짐
- 구간을 나누고, 구간에서 가장 큰 값이 있을 것임
- 가장 큰 값이 오름차순으로 되도록 구간을 나누는 경우의 수
접근법
- 앞에서부터 구간을 나누어놓으면, 뒷 구간 경우의 수는 정해질 것 같음
- 앞에 구간이 어떻게 나뉘었든 최대 값은 정해질 것임
- 서로다른 앞 구간에 대해서, 특정 지점에서 나뉘어졌다면, 뒷 구간의 경우의수는 중복일 것임 ==> DP 아이디어
- dp[k] : k 번째 위치에서 구간이 딱 끊겼을때, 앞으로 나올 수 있는 경우의 수
- 이때 k구간까지의 최대값보다 큰 값이 나오는 위치부터 경우의 수를 세어야한다.
- 6 3 ^ 1 7 2 5 4 8
- 1 / 7, .... 안됨
- 1 7 / 2 .... 됨
- 1 7 2 / .... 됨
- 6 3 ^ 1 7 2 5 4 8
- 일단 다음번 끊을 위치의 시작점은 알고, 그때 발생하는 경우의 수는 또 뒤에서 알아서 할 것임, 즉
- dp[k] = dp[p] + dp[p + 1] + ... dp[n], p는 k까지의 최대값보다 큰 수가 나타나는 최초 지점
- dp가 있긴 하지만 누적합이 사용되므로 누적합도 같이 관리
- subsum[k] = dp[k] + dp[k + 1] + .....
- subsum을 dp로 활용해서 구현해도 됨
- 1부터 연속되는 구간의 최대값을 별도의 배열에 저장함
- n부터 탐색하면서 최대값이 바뀌는 지점을 포착함 => k까지의 최대값보다 큰 수가 나타나는 최초지점으로 활용
newbieski