2075 : 잡 프로세싱(Job Processing)
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 7 회
- 시도횟수
- 31 회
문제
어떤 공장이 생산 라인이다. 생산 과정에는 A와 B라는 두 가지 공정이 이루어진다.
공장에는 각각의 공정을 수행하도록 되어있는 기계가 여러대 있다.
아래 그림은 생산라인의 구성 모습을 잘 보여주고 있다.
A공정을 하는 기계는 처음에 들어온 원료를 사용하여 이를 중간 생성물로 바꾼 뒤 이를 B공정을 맡은 기계에 넣는다.
B공정을 하는 기계는 중간 생성물을 더 가공하여 그것으로 완제품을 만든다.
단, 여기서는 원료 하나가 각각 중간 생성물과 완제품의 순서로 바뀐다.
모든 기계는 서로에게 영향을 주지 않고 같은 시간에 병렬식으로 따로따로 동작한다.
각 원료의 크기는 별 제한이 없으며, 개수만이 의미가 있다.
다만 기계들은 제각기 성능이 달라, 한 개의 원료를 처리하는 시간이 기계마다 서로 다를 수 있다.
모든 기계가 작업을 동시에 시작했을 때, N개의 원료가 모두 A과정을 마무리하는데 필요한 가장 짧은 시간을 계산하라.
그리고 N개의 원료가 모두 완제품으로 바뀌는데 걸리는 가장 짧은 시간도 계산하라.
입력형식
첫줄에 원료의 수 N(1≤N≤1,000), "A"공정을 처리하는 기계의 수 M1(1≤M1≤30), "B"공정을 처리하는 기계의 수 M2(1≤M2≤30)가 들어온다.
둘째 줄에는 M1개의 수가 나오며, 이것은 A공정의 각 기계가 원료를 중간 생성물로 바꾸는데 걸리는 시간이며, 이어서 M2개의 수가 나오는데 이것은 B공정의 각 기계가 중간 생성물을 완제품으로 바꾸는데 걸리는 시간이다. 각 기계의 시간 범위는 1~20이다.
출력형식
첫 번째로는 모든 원료가 A공정을 다 마치는 데 걸리는 최소 시간을 두 번째는 모든 원료가 완제품으로 바뀌는데 걸리는 최소 시간을 한 줄에 출력한다.
입력 예5 2 3 1 1 3 1 4 |
출력 예3 5 |