Informatica Online Judge

  0/1 뒤집기 [1839 / 072F]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 7   Total Tried : 19


The Champion of this Problem (C++) : gs17030 - 0ms / 3687byte
My Best Submission (C++) : N/A

[koistudy.net (JK Jeong 2017)]

Background

경곽이는 숫자뒤집기를 좋아한다.

n개의 0과 1로 구성된 숫자열이 주어진다.

이 숫자열 중 m개를 골라 뒤집을 수 있다. 이 때 m개의 숫자는 연속될 필요없이 임의의 위치에 있는 숫자들을 고를 수 있다.

이 숫자들을 뒤집으면 1은 0이 되고 0은 1이된다.

예를 들어 주어진 숫자열이

1 1 1

이고 2개를 뒤집을 수 있다면...

0 1 0 (1, 3번을 골라서 뒤집음)

이 될 수도 있고

0 0 1 (1, 2번을 골라서 뒤집음)

이 될 수도 있다.

이 게임의 목표는 모든 숫자를 0으로 만드는 최소 뒤집기 횟수를 구하는 것이다.

경곽이를 도와 이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n, m이 공백으로 구분되어 입력된다.

두 번째 줄에 n개의 0또는 1이 공백으로 구분되어 입력된다.

[입력값의 정의역]
3 <= n <= 100,000
1 <= m <= 100,000

Output

모두 0으로 만드는데 필요한 최소 뒤집기 횟수를 출력한다.

단, 모두 0으로 만들 수 없다면 -1을 출력한다.

IO Example

입력1
3 1
0 1 0

출력
1

* 설명
가운데 1을 뒤집으면 모두 0이되며 1회가 최소이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]