https://www.acmicpc.net/problem/23834
문제요약
- N개의 수가 두 번 주어짐(50만, 50만)
- 각각의 순서마다 양/음으로 이동을 할 수 있고, Ai만큼 가능함
- 최근 연속으로 M번 양으로 이동했으면, Bi만큼 이동하고 끝 (50만)
- 아니면 계속 이동...N번
- 이동하는 최대값
접근법
- 문제이해가 쉽지는 않았음. 특히 M번 이동하고 종료.
- 일단 B만큼 이동하는 상황이면 최근에 연속 M만큼 양으로 이동을 했을 것임
- 그리고 그 전에는 M 연속 양수 이동이 없어야하므로 일단 M 연속 바로 전은 음수 이동임
- 그렇다면 그 전에는 어떻게든 최선의 방법으로 이동을 했을 것임 => 어떻게든 이동을 하고, 음으로 이동, 연속 M 양수 이동은 가능하므로
- 최선의 방법 이동 = dp[] 로 둠
- 그렇다면 dp를 어떻게 전개할 것인가
- 최선의 방법 이동에서는 연속 M 양수 이동이 나타나서는 안됨
- 마지막이 음수, 그전이 음수, 그전전이 음수, .... 그 전 M -1 이 음수 가 가능해짐
- 그전 k 번째 음수 이동이면 값이 이렇게 됨 : 그전 k - 1까지 최선으로 이동 + k번째 음수 이동 + k + 1부터 양수 이동
- 저런 k 가 1 ~ M -1 까지 있을테고 그 중에 최대값을 찾으면 됨
- 최대값을 어떻게 찾나. M 번 반복하면 답없는데..
- 이 부분에서 생각이 어려웠음
- deque를 이용했고, 내림차순 정렬이 되게 유지를 했는데
- 이렇게 표현을 해보겠음. k 번째가 음수일때의 이동 최대값
- 그런데 특징이 있음 : ^(최선의 이동) -(음수이동) +(양수이동)
- 일단 아래의 후보에서 최대값을 알고 있다고 침
- [ ^ ^ ^ - + + +]
- [ ^ ^ ^ ^ - + +]
- [ ^ ^ ^ ^ ^ - +] ==> 이때가 최대
- [ ^ ^ ^ ^ ^ ^ -]
- 이 상황에서 값이 하나 더 추가되면 이렇게 됨
- [ ^ ^ ^ - + + + +]
- [ ^ ^ ^ ^ - + + +]
- [ ^ ^ ^ ^ ^ - + +] ==> 아까까지 최대
- [ ^ ^ ^ ^ ^ ^ - +]
- [ ^ ^ ^ ^ ^ ^ ^ -] ==> 새로 추가됨
- 일단 새로 추가된 것을 제외하면 아까까지 최대였던 것이 여전히 최대임 왜냐하면 오른쪽에 하나가 공통으로 추가되었으니까
- 새로 추가 된 것은 값이 얼마인지는 모르겠으나 앞에 있던 것들과 비교는 가능함 왜냐하면 음수인 부분을 알기때문에 부분합으로 계산이 가능함
- 따라서 최대인 것을 deque에 유지해나가면서 진행이 가능함
- 다만 기존에 있던 것들이 범위를 벗어나면 빼주면 됨 ==> 음수인 부분이 범위 밖이면 의미가 없기때문에 빼줌
- 이를 통해서 dp[] 값을 구할 수 있음
- 예외들
- 초기 M - 1까지는 음수로 이동할 필요는 없음. 어짜피 M번 연속 양수 이동은 불가능 하니까
- K번째에서 B로 점프하고 끝나는 것중에 최대가 최적의 값이라고 생각했음. 왜냐하면 항상 마지막에 연속 이동하고 점프하는 것이 이득이라고 생각 했음
- 하지만 다음과 같은 경우는 아님
- 굳이 마지막에 점프하지 않고, 3번, 3번 이동하는 것이 이득임
- 7 4
- 10 10 10 1 10 10 10
- 1 1 1 1 1 1 1
- 따라서 dp[N] 값과 [M..N] 시점에서 점프했을때의 최대값과 비교를 해야함
추가 고민
- 구간트리로도 접근을 하는 것 같은데 궁금함
- 엄청 어려웠음
newbieski