조선시대에는 임금님에게 상소문을 보낼 때 말을 이용하여 상소문을 전달하였고 이를 파발마라고 불렀다. 파발마들은 지방의 역에서 관리되었고 한 지방역에서 파발마를 이용하여 다른 지방역으로 상소문을 전달하면 다른 지방역에서 파발마를 이 용하여 또 다른 지방역으로 상소문을 전달하는 식 으로 몇 개의 지방역을 거쳐서 한양역까지 전달하 는 것이다.
조선에는 전국에 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냥의 비용이 든다.
여러분은 지방역의 수와 각 지방역의 상태를 입력 받아서 모든 상소문을 한양역으로 전달하는 데 필요한 최소의 비용을 출력하는 프로그램을 작성하라. 말은 모든 지방역에 충분히 많이 있다고 가정 한다.
수행 시간은 1초를 넘을 수 없다. 메모리 제한은 64MB이다.
입력 5 0 1 1 0 0 출력 9 입력 10 1 0 0 1 0 1 0 0 0 1 출력 22
출처: 제31회 한국정보올림피아드 전국본선 (2014.7.11) 고등부 문제3대회 풀이