COCI 2014/2015 contest7 3- ACM(ACM) > 문제은행 : 정보올림피아드&알고리즘




2622 : ACM(ACM)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
15 회   
시도횟수
31 회   

문제

국제 대학생 프로그래밍 경시대회(ACM-ICPC : Association for Computing Machinery-International Collegiate Programming Contest)는 학생 3명과 코치 1명이 1조를 이루어 대회에 참가한다. 팀당 컴퓨터를 한 대만 사용할 수 있으므로 여러 문제를 3명이 어떻게 나누어 푸느냐가 중요하다.

 

여기 ACM-ICPC 에 참여하게 된 한 팀이 있다.
이 팀의 코치는 필승(?)의 전략을 세웠다. 문제를 받으면 먼저 3명의 선수가 각각 문제를 읽고 각자가 생각하는 난이도를 1(쉬움) ~ 5(어려움) 단계로 표시한다.
그리고 문제의 순서를 변경하지 않고 3부분으로 나누어 3명에게 분배한다. 나눌때는 어느 누구도 1문제 이상을 배정받아야 하고, 2개 이상의 문제를 배정받을 때는 연속된 구간의 문제들을 받는다고 가정한다.
위와같은 기준으로 나눌 때 난이도의 합이 최소가 되게 나누는 것이 이 팀의 전략이다.

 

이 팀이 문제를 받고 3명의 팀원이 문제별 난이도를 표시한 결과가 주어질 때 최소가 되는 난이도의 합을 구하는 프로그램을 작성하시오.


입력형식

첫 행에 문제 수 N(3 <= N <= 150,000)이 주어진다.다음 3개의 행에 걸쳐 각 학생이 생각하는 각 문제의 난이도가 행 별로 N개씩 공백으로 구분되어 주어진다. 난이도의 범위는 1이상 5이하의 정수이다.

출력형식

최소가 되는 난이도의 합을 구하여 하나의 정수로 출력한다.

입력 예

3
1 3 3
1 1 1
1 2 3

출력 예

4

입력 예

7
3 3 4 1 3 4 4
4 2 5 1 5 5 4
5 5 1 3 4 4 4

출력 예

19

Hint!

입력 예 1에서 첫 번째 학생이 1번 문제를, 두번째 학생이 3번 문제를, 세 번째 학생이 2번 문제를 배정받으면 난이도의 합이 4로 최소가 된다. 입력 예 2에서는 첫 번째 학생이 4, 5, 6, 7번 문제를 두 번째 학생이 1, 2번 문제를 세 번째 학생이 3번 문제를 배정받으면 난이도의 합이 19로 최소가 된다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP