Informatica Online Judge

  피라미드 사발 뒤집기 [1238 / 04D6]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 26   Total Tried : 40


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

[JKJeong 2015]

Background

다음 그림과 같이 피라미드 형태로 사발이 놓여있다.

"0"은 정상상태, "1"은 뒤집어진 상태를 나타낸다.

1
1 0
1 0 1

이와 같이 사발이 주어질 때, 가장 꼭대기로부터 왼쪽 또는 오른쪽으로 내려오면서 사발을 하나씩 가져올 수 있다.

예를 들어 꼭대기에서 처음에는 왼쪽으로, 다음에는 오른쪽으로 이동하면

"110"

과 같은 사발열을 얻을 수 있다.

이와 같이 얻은 사발열을 "000"으로 만드는 것이 목적이다. (이 내용은 사발뒤집기 문제를 풀어보면 쉽게 알 수 있다.)

n개의 사발이 있는 사발열에서 사발을 뒤집는 규칙은 다음과 같다.

- k번 사발을 뒤집으면 k-1, k, k+1 사발이 동시에 뒤집어 진다. ( 1 <= k <= n-1 )
- 1번 사발을 뒤집으면 1, 2번 사발이 동시에 뒤집어 진다.
- n번 사발을 뒤집으면 n-1, n번 사발이 동시에 뒤집어 진다.

이와 같은 방법으로 "110"사발을 모두 0으로 만들기 위해서는

1번 사발을 뒤집으면 된다. 즉 1회의 뒤집기로 모두 0으로 만들 수 있다.

주어진 피라미드 사발탑 꼭대기에서 바닥까지 내려오면서 만든 사발열을 모두 뒤집는데 드는 최소 횟수를 구하시오.

주어진 그림에서 얻을 수 있는 사발열은 모두 다음과 같다.

- 1 1 1
- 1 1 0
- 1 0 0
- 1 0 1

각 사발열들을 뒤집는 횟수를 구하면 다음과 같다.

- 1 1 1 -> 0 0 0 (2번 사발을 뒤집음) 1회로 가능
- 1 1 0 -> 0 0 0 (1번 사발을 뒤집음) 1회로 가능
- 1 0 0 -> 1 1 1 (3번 사발을 뒤집음) -> 0 0 0 (2번 사발을 뒤집음) 2회로 가능
- 1 0 1 -> 1 1 0 (3번 사발을 뒤집음) -> 0 0 0 (1번 사발을 뒤집음) 2회로 가능

따라서 최소로 가능한 횟수는 1회이다.

Input

첫 번째 줄에 피라미드의 높이를 나타내는 정수 n이 주어진다.

두 번째 줄부터 n줄에 걸쳐서 각 줄에 n개씩의 사발의 상태가 공백으로 구분되어 입력된다.

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

Output

피라미드로부터 만들 수 있는 사발열들 중 모두 뒤집는데 최소횟수를 출력한다.

만약 답이 없다면 즉, 뒤집을 수 없다면 -1을 출력한다.

IO Example

입력
3
1
1 0
1 0 1

출력
1

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