Lv.2binary-searchgreedyparametric-search
제품 K개 만들기
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
공장에 기계 대가 있습니다. 모든 기계는 0분에 동시에 가동을 시작하고, 서로 독립적으로 움직입니다.
번째 기계는 가동 시작 후 분에 첫 제품을 완성하고, 그 뒤로는 분마다 제품 하나를 완성합니다. 즉 번째 기계가 제품을 완성하는 시각은
입니다.
제품을 모두 합쳐 개 완성하려면 최소 몇 분이 걸리는지 구하세요.
매개변수
A—A[i]는 번째 기계가 제품 하나를 더 만드는 데 걸리는 시간(분)B—B[i]는 번째 기계가 첫 제품을 완성하는 시각(분)K— 완성해야 하는 제품의 총 개수
입출력 예
| A | B | K | result |
|---|---|---|---|
[3] | [0] | 5 | 12 |
[2, 3] | [0, 0] | 5 | 4 |
[1, 100] | [50, 0] | 3 | 51 |
입출력 예 설명
예 1 — 기계가 하나뿐이고 0분, 3분, 6분, 9분, 12분에 제품을 완성합니다. 5개째가 완성되는 시각은 12입니다.
예 2 — 시각별 누적 생산량입니다.
| 시각 | 1번 기계 | 2번 기계 | 누적 |
|---|---|---|---|
| 0 | 1개 | 1개 | 2 |
| 2 | 2개 | 1개 | 3 |
| 3 | 2개 | 2개 | 4 |
| 4 | 3개 | 2개 | 5 |
4분에 5개가 되므로 답은 4입니다.
예 3 — 2번 기계가 0분에 1개를 만들고, 1번 기계가 50분과 51분에 하나씩 만들어 51분에 3개가 됩니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
Function signature
solution(A: int[], B: int[], K: int) → long
Constraints
A.length == B.length == N- 답은 최대 까지 커질 수 있으므로 64비트 정수를 쓰세요.
Expected complexity
- Time
- O(N log(answer))
- Space
- O(1)
Examples
| A | B | K | Expected |
|---|---|---|---|
[3] | [0] | 5 | 12 |
[2,3] | [0,0] | 5 | 4 |
[1,100] | [50,0] | 3 | 51 |
Hint
Hint
답을 직접 구하는 공식은 없지만, 시각 가 주어지면 그때까지 완성된 제품 수는 쉽게 셀 수 있습니다. 번째 기계는 일 때 개를 완성합니다.
그리고 가 커질수록 완성 개수는 줄어들지 않습니다(단조성). 그러니 답 자체를 이분탐색할 수 있습니다.
주의할 점 두 가지입니다.
- 탐색 상한은 정도로 넉넉히 잡으세요.
- 개수의 합이 64비트도 넘칠 수 있습니다. 에 도달하면 즉시 세기를 멈추세요.
복잡도 목표
제품을 하나씩 꺼내며 시뮬레이션하는 풀이는 가 최대일 때 효율성 테스트에서 시간 초과가 납니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 3 | verdict only |