30874번 - Pipelined 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 423 | 275 | 234 | 69.643% |
문제
현대자동차에서 근무하고 있는 로하는 주어진 작업 슬롯 하나로 $N$개의 자동차를 생산하는 공정을 계획하려 한다. 각 $i$번째 자동차는 생산하기 위해 $s_i$단계의 생산 프로세스를 거쳐야 한다. 작업 슬롯은 수직선상에서 $\left[ 0,1 \right)$로 표현할 수 있으며, $i$번째 자동차 생산이 진행 중인 경우 이 중 $\frac{1}{s_i}$ 크기의 반열린 구간을 차지한다. $0$초부터 시작해서 $1$초마다 다음과 같은 일이 순서대로 일어난다.
- 먼저 할당된 생산 프로세스부터, 작업 슬롯의 모든 생산 프로세스들은 자신의 크기만큼 뒤로 움직인다. 즉, 작업 슬롯의 전체 구간을 $\left[ 0,1 \right)$로 표현했을 때, $i$번째 생산 프로세스가 $\left[ \frac{j-1}{s_i} ,\frac{j}{s_i} \right)$의 구간을 차지하고 있었다면, 이동 후 $\left[ \frac{j}{s_i} ,\frac{j+1}{s_i} \right)$의 구간을 차지하게 된다. 단, 이동 시 다른 생산 프로세스가 차지하는 구간과 겹치게 되는 경우에는 움직이지 않는다. 슬롯을 통과하여 $[0,1)$ 밖으로 나온 경우 이 생산 프로세스는 완료된 것이며, 더 이상 공간을 차지하지 않는다.
- 로하는 아직 할당하지 않은 생산 프로세스 중 하나를 골라 슬롯에 할당하거나 할당하지 않을 수 있다. $i$번째 생산 프로세스를 할당할 경우 슬롯의 $\left[ 0,\frac{1}{s_i} \right)$ 부분에 생산 프로세스를 할당한다. 단, 다른 생산 프로세스가 차지하고 있는 구간과 겹치는 경우 할당할 수 없다.
모든 자동차가 작업 슬롯을 거쳐 생산될 때까지 걸리는 최소 시간이 몇 초인지 구하여라.
입력
첫 번째 줄에 생산해야 하는 자동차의 개수 $N$이 주어진다. $(1\leq N\leq 200\, 000)$
두 번째 줄에 $N$개의 자동차의 생산 프로세스에 대한 각각의 단계 수 $s_1,s_2,\ldots ,s_N$이 공백으로 구분되어 주어진다. $(1\leq s_i\leq 200\, 000)$
출력
첫 번째 줄에, 모든 자동차가 작업 슬롯을 거쳐 끝날 때까지 걸리는 최소 시간을 초 단위로 출력한다.
예제 입력 1
4 5 7 8 11
예제 출력 1
14
노트
반열린구간 $[a, b)$ 는 $a$ 이상 $b$ 미만의 모든 수를 포함하는 구간이다.
출처
University > 한양대학교 > 제10회 한양대학교 프로그래밍 경시대회(HCPC) > Beginner Division G번
- 문제를 만든 사람: mnx
- 문제를 검수한 사람: andrewmjk1, cologne, hjroh0315, mjhmjh1104, naeby, seonah, solvedac, yijw0930
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | ���제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호