[고등부] 2024 KOI 2차대회 대비 모의고사 (1주차)

N 개의 스위치가 있다. 각 스위치의 상태는 0 또는 1 이다.

• 상태 0 인 스위치를 누르면 1 이 되고,

• 상태 1 인 스위치를 누르면 0 이 된다.

안타깝게도 스위치의 크기가 너무 작고 손가락은 굵어서 어떠한 스위치를 누를 때 연속된 K개의 스위치가 함께 눌린다.

가장자리에 있는 스위치의 경우 벽에 인접해 있기에 마찬가지로 개별적으로 누르는 것이 불가능하고 무조건 K개가 함께 눌린다.

예를 들어 K = 3 이고 N=6 인 스위치의 상태가 0\ 0\ 1\ 0\ 0\ 1 인 경우 아래와 같이 두 번 누르면 모든 스위치를 0으로 만들 수 있다

초기 상태 : 0\ 0\ 1\ 0\ 0\ 1

한번 누름 : 0\ 0\ 0\ 1\ 1\ 1

두번 누름 : 0\ 0\ 0\ 0\ 0\ 0

N과 K 그리고 N개의 스위치 상태를 입력 받았을 때, 모든 스위치의 상태가 0이 되도록 스위치를 누르는 최소 횟수를 출력하자.