BOJ 10350 - 은행

문제 링크 : https://www.acmicpc.net/problem/10350

문제 풀이

맨처음에 문제를 딱 보고서 떠오른 생각은 가장 작은 값에서 "행동" 을 실행하는 것을 반복하면 될 것이라고 생각했다. exchange argument에 의해서 가장 작은 값의 위치에서 실행하는 것이 더 손해를 볼 일은 없다고 생각했다. 그래서 좀 더 고민을 해보다가 다른 생각이 떠오르지 않아 구현을 시작했고, 결과는 pq에 담으니 mle가 뜨게 되었다. 

 이를 보고서 절댓값의 감소량을 추적해보니 얼마 되지 않는다는 것을 알 수 있었다. 따라서 답은 굉장히 크다는 것을 알 수 있었고, 어떻게 해도 직접 "행동"을 한 번씩 해가면서 변화를 보는 것은 답이 될 수 없겠다고 판단하였다. 이 상황에서 내가 나아갈 수 있는 방향은 2가지라고 판단했다. 
1. 한번에 여러번의 행동씩을 처리하여 답을 얻어내기. 즉, 행동과정을 묶어서 처리하기.
2. 답과 동치인 다른 값을 알아내어, 계산이 가능한 그 값을 계산하는 문제로 바꾸어내기.  

 일단 예제부터 살펴보았다. 가장 앞에 있는 음수부터 행동을 취해도, 가장 뒤에 있는 음수부터 행동을 취해도, 임의의 순서로 행동을 취해도 같은 횟수가 걸리는 것을 확인할 수 있었다. 다른 예제도 만들어서 본 결과 아마도 행동하는 순서에 관계없이 같은 결과를 얻게 될 것이라고 추측하였다. 

 나의 문제 풀이 스타일은 2번에 굉장히 강점이 있지만, 위와 같은 사실을 얻은 이상 일단 1번의 풀이 방식을 시도하지 않을 수 없었다. 1~i를 처리하기, (a , b)의 음양, 절댓값 크기 case 에 따른 줄이기 모두 실패했고, 구간합이 음수인 구간에 모두 한번 씩 행동을 취할 수 있다는 사실을 알아냈다. 하지만 결국 길이가 k인 구간합이 음수인 구간을 한 번에 처리하면 변하는 값의 갯수가 O(K)이기 때문에 딱히 달라지는 부분이 없었다. 여기까지 도달해보니 지금 당장은 1번 방식의 풀이가 딱히 좋지 못하다고 느껴졌고, 그래서 2번으로 옮겼다. 

 2번의 방식에서 내가 좋아하고 잘 사용하는 방식은 작은 예제를 손으로 따라가면서 직접 해보면서 그 과정에서 관찰을 하는 것이다. 그래서 나는 (3 -1 -1) 에 대해서 시도를 해보았다. (3 -1 -1) (2 1 -2) (0 -1 2) (-1 1 1) (1 0 0) 한 번의 과정으로 4개의 시작에 대한 결과를 한 번에 얻어낼 수 있었다. 이 과정에서 (3 -1 -1) 과 (2 1 -2) 에서 값이 1차이 나고 (2 1 -2)과 (0 -1 2)에서 값이 1차이 나고.... 이런 것은 어떤 값이 있을까를 여러 예제에서 실시했다. 여기서 이전에 연관이 조금이라도 있었던 음수 구간합에 집중을 해서 살펴보았다.
(3 -1 - 1) - (구간합 -1, -1, -2 존재) (2 1 - 2) - (구간합 -1, -2 존재) (0 -1 2) - (구간합 -1, -1 존재) (-1 1 1) - (구간합 -1 존재).
와! 음수 구간합의 합이 횟수와 똑같다는 사실을 확인할 수 있었다. 다른 몇 가지 경우에 대해서도 되는 것을 확인했지만, (-2, 1, 1, 1) - 4회. (-2, 1, 1, 1, 1) - 3회. (-2, 1, 1, 1, 1, 1, ...) - 3회. 의 경우에서 내가 생각한 반례를 찾을 수 있었다. 이를 통해서 전체 합이 연관 되어 있다고 추측을 하였고, (5 -2 -1) 에 대해서 다시 한번 시도하였다. 
여기서 -2 가 1회의 가치를 지니는 것을 확인할 수 있었다. 전체 합이 2인 것을 생각하면 굉장히 연관성이 있는 수치였다.

지금까지 여러 예제들을 돌려본 결과 내가 예상하기로 답은 ((|음수 구간합| / 전체합)의 올림)의 합 과 같다고 추측하였다. 이를 구하기 위하여 세그먼트 트리를 어케 써야 하는지에 대해서 고민을 하고 있었는데, 알고보니 범위가 n^2이 가능한 제한이었다. 바로 구현 후 AC를 받을 수 있었다.