Informatica Online Judge

  파발마 #4 [1065 / 0429]

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


The Champion of this Problem (C++) : gst19076 - 2ms / 1235byte
My Best Submission (C++) : N/A

[KOI 2014 고등부 (데이터 제작 31st Kenny Park)]

Background

조선시대에는 임금님에게 상소문을 보낼 때 말을 이용하여 상소문을 전달하였고 이를 파발마라고 불렀다.

파발마들은 지방의 역에서 관리되었고 한 지방역에서 파발마를 이용하여 다른 지방역으로 상소문을 전달하면 다른 지방역에서 파발마를 이용하여 또 다른 지방역으로 상소문을 전달하는 식으로 몇 개의 지방역을 거쳐서 한양역까지 전달하는 것이다.

조선에는 전국에 N개의 지방역이 있고 이 역들과 한양역을 모두 연결하는 N+1개의 도로가 원모양으로 연결되어 있다.

따라서 각 역들은 항상 2개의 역과 인접한다. 한양역이 원형의 꼭대기에 있는 것으로 가정하고 각 지방역은 한양역에서 시계방향으로 1번부터 시작하여 번호가 붙은 것으로 생각한다. 아래 그림은 N=5인 경우의 예이다.



상소문은 하루에 인접한 역으로만 이동할 수 있으며 이동하지 않고 머물러 있는 것도 가능하다. 위의 그림처럼 어느날 역 3에 상소문이 있으면 그 다음날에는 역 2이나 역 4로 이동할 수 있으며 역 3에 머물러 있는 것도 가능하다.

한 역에 여러 개의 상소문이 함께 모여 있을 수 있으며 한 마리의 파발마로 여러 개의 상소문을 한꺼번에 이동하는 것도 가능하다.

여러분은 어떤 날 지방역들의 상태를 받게 된다. 각 지방역은 하나의 상소문을 가지고 있거나 없거나 둘 중 하나의 상태이다.

이 상소문을 한양역으로 보내야 하는데, 말 한 마리를 하루 사용하면 상소문 개수에 상관없이 1냥의 비용이 든다. 그리고 상소문마다 비용이 발생하는데 하나의 상소문이 한양역까지 이동하는데 D일이 걸리면 D냥의 비용이 든다.

이 때 처음이나 중간에 머무르는 날도 한양역으로 이동하는 날에 포함된다.

위의 그림의 경우 역 3에 있는 상소문을 역 2로 먼저 이동한 후에 두 상소문을 함께 역 2에서 역 1로 그리고 한양역으로 이동하는 경우의 비용을 계산해 보자.

먼저 첫날 역 3의 상소문을 역 2로 이동하기 위해 파발마 1마리를 사용하고 다음날 역 2의 상소문 2개를 역 1로 이동하기 위해 파말마 1마리를 사용한다.

3일째에는 역 1의 상소문 2개를 한양역으로 이동하기 위해 파발마 1마리를 사용한다.

결론적으로 총 3일 동안 매일 한 마리의 파발마를 사용하므로 3냥의 비용이 들고 두 개의 상소문이 한양역에 도착하는데 3일씩 걸리므로 6냥의 비용이 필요하여 총 9냥의 비용이 든다.

여러분은 지방역의 수와 각 지방역의 상태를 입력 받아서 모든 상소문을 한양역으로 전달하는 데 필요한 최소의 비용을 출력하는 프로그램을 작성하라.

말은 모든 지방역에 충분히 많이 있다고 가정한다.

Input

입력의 첫 줄에는 지방역의 수 N이 주어진다. 다음 줄에는 숫자 N개가 주어지는데 1번 역부터 순서대로, 그 역에 상소문이 있는 경우에는 1이, 없는 경우에는 0이 공백을 사이에 두고 주어진다.

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

[Sub-task Info]
#1 : N <= 20 (11%)
#2 : N <= 500 (26%)
#3 : N <= 5,000 (21%)
#4 : 추가제한조건 없음 (42%)

Output

출력은 단 한 줄이며, 최소 비용을 정수로 출력한다. 비용의 값이 커질 수 있으므로 64비트 정수 변수 (long long)를 사용해야 할 수도 있음에 주의하라.

IO Example

입력
5
0 1 1 0 0

출력
9

입력2
10
1 0 0 1 0 1 0 0 0 1

출력2
22

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