[BOJ] 11577번: Condition of deep sleep

copyrat90·2022년 3월 20일
0

PS

목록 보기
3/5

문제 설명

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

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

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

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

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

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

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

7 3
1 0 1 0 1 0 1

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

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

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

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

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

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

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

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

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

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

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

정답 코드 : O(N)O(N)

비슷한 문제

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


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

profile
요새 알고리즘 문제 푸는 초보A

0개의 댓글