문제 설명

이 문제는 2단계로 생각해야 하는 문제다.

1. Naive $O(NK)$ 그리디 풀이 떠올리기
2. 위 풀이를 큐를 이용해 $O(N)$으로 최적화

1. $O(NK)$ 그리디 풀이 아이디어

편의를 위해 $[i, i+K)$ 범위의 연속된 전구를 끄는 행위를 $Toggle(i)$ 라고 부르도록 하자.

당연히, 같은 범위의 전구를 2번 뒤집는 건 의미가 없다.
켜졌다 꺼질 것이라면 애초에 안 켜면 되니까...

따라서 최적의 경우, 특정 $i$에 대해 $Toggle(i)$는 1번 하거나, 0번 할 것이다.

예제 입력이 아래와 같이 $N=7, K=3$ 인 경우를 보자.

7 3
1 0 1 0 1 0 1

$i=0$번째 전구가 켜져있으므로 꺼야 하는데, $Toggle(0)$ 밖에는 끌 방법이 없다.
고로 $Toggle(0)$을 무조건 1번 하게 되어있다.

그런데, 그렇게 하면 $i=1$번째 전구가 켜진다.
이걸 끄려면? 이번에도 $Toggle(1)$ 밖에는 끌 방법이 없다.
왜냐하면 이미 $Toggle(0)$ 은 1번 해버려서, 한 번 더 하는 것은 의미가 없기 때문이다.

즉, 전구 배열을 $[0,N-K)$까지 순회하면서,
$i$번 전구가 켜져있으면 그리디하게 $Toggle(i)$하는 풀이가 가능하다.

그런데 상식적으로 생각해봤을때, $Toggle(i)$ 한번 하려면 K개의 전구를 꺼야하니 $O(K)$가 걸린다.
그런데 만일 모든 범위를 $Toggle$ 해야하는 입력이 주어지면? $O(NK-K^2)$로 시간 초과다.

2. 큐를 이용해 $O(N)$으로 최적화

그러면 $Toggle(i)$를 어떻게든 최적화해야 한다는건데... 이게 가능할까?
왜 이렇게 오래 걸리는지를 곰곰히 생각해보자.

$i$번째 전구의 입장이 돼서 생각해보면, 모든 범위를 $Toggle$ 해야하는 입력의 경우
$Toggle(i-K+1), Toggle(i-K+2), ... , Toggle(i-1), Toggle(i)$
위처럼 총 $K$개의 $Toggle$ 호출마다 꺼졌다 켜졌다, flip되기를 반복할 것이다.

$i$번째 전구를 상수 횟수만 flip되도록 하는 방법이 없을까?
큐를 이용해, 딱 2번으로 제한하는 방법이 있다.

매 반복마다 뒤에 있는 $K$개의 전구를 매번 끄는 대신에, $i$번에 끈다면, $i+K-1$까지 flip되었다는 상태를 큐에 저장하자.

$i$번째 반복에선 우선 큐에서 $i$번 이전 idx를 전부 pop() 해 지나간 반전을 무효화하고,
큐에 들어있는 원소의 개수가 짝수이면 flip의 flip이므로 현재 상태 그대로,
홀수이면 flip이므로 현재 상태를 반전시킨 다음 끌지 말지를 판단하자.

이러면 $i$번째 원소는 최대 $2$번 반전되므로, $O(N)$만에 해결 가능하다.

정답 코드 : $O(N)$

비슷한 문제

19644번: 좀비 떼가 기관총 진지에도 오다니

---

꽤나 까다로운 문제였다. 푸는데 40분 걸렸다...
사실 소스에 주석으로 아이디어를 전부 적느라 시간이 오래 걸리긴 했다만.