http://gall.dcinside.com/board/view/?id=programming&no=591459


이거 생각나서 올림


일단 그리디


핵심 아이디어는 같은 구간을 n 번 반전 시키는건 n % 2번 반전 시키는것과 같다는거 (즉 같은 구간을 한번 이상 반전 시킬 이유는 없음), 그리고 반전하는 순서는 상관 없음.


그럼 첫번째 전구를 보자. 첫번째 전구가 켜저 있으면 1 - K 구간은 꼭 반전을 시켜야 함. 반대로 첫번째 전구가 꺼져 있으면 반전을 시키면 안됨. 왜냐면 첫번째 전구를 포함하는 구간은 1-K 구간 밖에 없기 때문.


두번째 전구, 세번째 전구, 등도 똑같은 룰을 적용 할수 있음. 즉 그리디 속성을 만족한다는거.


나이브하게 풀면 O(NK) 인데 간단하게 O(N)으로 줄일수 있음. 이건 님이 생각해보셈.