| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 1228 | 719 | 619 | 60.039% |
한국정보기술진흥원의 직원들은 6개월에 한 번 씩 전 직원이 사장님과 일대일 면담을 진행한다.
진흥원에는 $N$개의 부서가 있는데, 부서에 소속된 모든 직원이 모두 면담을 마쳐야 해당 부서가 퇴근할 수 있다고 한다. 면담은 한 번에 한 명씩만 진행된다.
모든 부서의 퇴근 시간의 합이 최소가 되는 값을 구하시오.
첫 번째 줄에 부서의 수 $N$ (1ドル \le N \le 1000$)이 주어진다.
두 번째 줄부터 $N$개의 줄에 걸쳐서 부서별 직원의 수와 직원당 면담에 소요되는 시간이 공백으로 구분되어 주어진다. 단, 모든 부서의 직원 수의 합은 1ドル,000円,000円$명 이하이며, 직원당 면담에 소요 되는 시간은 1ドル$분 이상 1ドル,000円$분 이하의 정수이다.
모든 부서의 퇴근하는 데 걸리는 시간의 합의 최솟값을 분 단위로 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $N ≤ 2$ |
| 2 | 29 | 직원 수의 합 $\le 1,000円$ |
| 3 | 64 | 추가 제한 없음 |
3 2 5 50 2 20 10 1 100
300
부서 1ドル$에는 2ドル$명의 직원이 있고 각 직원의 면담 소요 시간은 5ドル$분, 50ドル$분이다.
부서 2ドル$에는 2ドル$명의 직원이 있고 각 직원의 면담 소요 시간은 20ドル$분, 10ドル$분이다.
부서 3ドル$에는 1ドル$명의 직원이 있고 각 직원의 면담 소요 시간은 100ドル$분이다.
이때 면담 순서를 부서2ドル$직원2ドル$ → 부서2ドル$직원1ドル$ → 부서1ドル$직원1ドル$ → 부서1ドル$직원2ドル$ → 부서3ドル$직원1ドル$ 순서로 하면 부서2ドル$의 퇴근 시간은 10ドル+20=30$분, 부서1ドル$의 퇴근 시간은 10ドル+20+5+50=85$분, 부서3ドル$의 퇴근 시간은 10ドル+20+5+50+100=185$분으로 총합은 30ドル+85+185=300$분이다.
Contest > 한국정보기술진흥원 > 제1회 청소년 IT경시대회 > 예비소집 B번