파발마 > 문제은행

본문 바로가기


문제은행

2799 : 파발마

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 31회    시도횟수: 298회   



조선시대에는 임금님에게 상소문을 보낼 때 말을 이용하여 상소문을 전달하였고 이를 파발마라고 불렀다. 파발마들은 지방의 역에서 관리되었고 한 지방역에서 파발마를 이용하여 다른 지방역으로 상소문을 전달하면 다른 지방역에서 파발마를 이용하여 또 다른 지방역으로 상소문을 전달하는 식으로 몇 개의 지방역을 거쳐서 한양역까지 전달하는 것이다.


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


ba614cd53af700808b5d91c52f79cea9_1454391 


상소문은 하루에 인접한 역으로만 이동할 수 있으며 이동하지 않고 머물러 있는 것도 가능하다. 위의 그림처럼 어느날 역 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냥의 비용이 든다.

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


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

<제약조건>
• 부분문제 1: 전체 점수 100점 중 11점에 해당하며 N ≤ 20 이다.
• 부분문제 2: 전체 점수 100점 중 26점에 해당하며 N ≤ 500 이다.
• 부분문제 3: 전체 점수 100점 중 21점에 해당하며 N ≤ 5,000 이다.
• 부분문제 4: 전체 점수 100점 중 42점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.


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

[Copy]
5
0 1 1 0 0
[Copy]
9


[Copy]
10
1 0 0 1 0 1 0 0 0 1
[Copy]
22




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.