Informatica Online Judge

  컵 복구하기 [1133 / 046D]

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


The Champion of this Problem (C++) : gs17089 - ms / 509byte
My Best Submission (C++) : N/A

[koistudy.net (T. HS Jeon)]

Background

n개의 컵이 일렬로 나열되어 있다.

컵이 바르게 된 것도 있고 뒤집어진 것도 있다.

바르게 된 컵을 1, 뒤집어진 컵을 0 이라고 나타낸다.

만약 컵이 6개가 있으며,

0 0 1 1 1 1

로 되어 있다면, 앞에 있는 2개의 컵은 뒤집어 진 것이고, 나머지 4개의 컵은 바로 된 것이다.

이 문제의 목적은 모든 컵을 바른상태(모두 1)로 만드는 것이다.

단 할 수 있는 동작은 주어진 컵들 중 임의의 컵을 5개 골라 모두 뒤집을 수 있다.

단, 컵은 인접하지 않아도 상관없다.

예를 들어 위의 경우라면 두 번째 컵을 제외한 모든 컵을 뒤집으면

1 0 0 0 0 0

의 상태가 된다.

다음으로 1번을 제외한 5개의 컵을 뒤집으면

1 1 1 1 1 1

로 되며 정리가 완료된다. 이 때 2번의 동작으로 모든 컵을 정리했다.

컵의 수와 현재 상태가 주어질 때, 정리하는데 드는 최소 동작 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 컵의 수 n이 입력된다.

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

[입력값의 정의역]
5 <= n <= 1,000

Output

컵을 정리하는데 드는 최소 동작의 수를 출력한다. 만약 정리를 완료할 수 없는 상태라면 -1을 출력한다.

IO Example

입력
6
0 0 1 1 1 1

출력
2

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