CodeForces Round 843 E. The Human Equation

문제 요약

수열이 주어진다. 해당 수열에 다음과 같은 연산을 할 수 있다.

1. 수열에서 임의의 부분수열(subsequence)를 고른다

2. 부분수열의 홀수 번째 원소에 +1, 짝수 번째 원소에 -1을 하거나, 홀수 번째 원소에 -1, 짝수 번째 원소에 +1을 한다.

전체 수열의 모든 원소를 0으로 만들기 위한 연산의 필요 최소 횟수를 구하라.

 

풀이

풀이가 매우 간단하지만 나름대로의 인사이트가 있는 거 같아서 가져와봤다.

먼저 누적합 배열을 생각해보자. 주어진 연산은 이 누적합 배열의 부분수열에 1을 더하거나 빼는 것으로 바꿔서 생각할 수 있다. 원래 배열의 i번째 원소에 1을 더하고 j번째 원소에 1을 뺀다면(i<j), 누적합 배열에서는 [i, ... j-1]에 1이 더해지기 때문에, 원하는 구간을 모두 색칠할 수 있고, 반대도 마찬가지이다. 따라서 누적합 배열에서의 최댓값-최솟값이 답이 된다.

풀이가 엄청 간단한데 떠올리기 쉽지 않은 것 같아서 가져와봤다.