Funcia
Lv.2binary-searchgreedyparametric-search

제품 K개 만들기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

공장에 기계 NN대가 있습니다. 모든 기계는 0분에 동시에 가동을 시작하고, 서로 독립적으로 움직입니다.

ii번째 기계는 가동 시작 후 B[i]B[i]분에 첫 제품을 완성하고, 그 뒤로는 A[i]A[i]분마다 제품 하나를 완성합니다. 즉 ii번째 기계가 제품을 완성하는 시각은

B[i],  B[i]+A[i],  B[i]+2A[i],  B[i]+3A[i],  …B[i],\; B[i]+A[i],\; B[i]+2A[i],\; B[i]+3A[i],\; \dots

입니다.

제품을 모두 합쳐 KK개 완성하려면 최소 몇 분이 걸리는지 구하세요.

매개변수

  • A — A[i]는 ii번째 기계가 제품 하나를 더 만드는 데 걸리는 시간(분)
  • B — B[i]는 ii번째 기계가 첫 제품을 완성하는 시각(분)
  • K — 완성해야 하는 제품의 총 개수

입출력 예

ABKresult
[3][0]512
[2, 3][0, 0]54
[1, 100][50, 0]351

입출력 예 설명

예 1 — 기계가 하나뿐이고 0분, 3분, 6분, 9분, 12분에 제품을 완성합니다. 5개째가 완성되는 시각은 12입니다.

예 2 — 시각별 누적 생산량입니다.

시각1번 기계2번 기계누적
01개1개2
22개1개3
32개2개4
43개2개5

4분에 5개가 되므로 답은 4입니다.

예 3 — 2번 기계가 0분에 1개를 만들고, 1번 기계가 50분과 51분에 하나씩 만들어 51분에 3개가 됩니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(A: int[], B: int[], K: int) → long

제한 사항

  • 1≤N≤1,0001 \le N \le 1{,}000
  • A.length == B.length == N
  • 1≤A[i]≤1091 \le A[i] \le 10^9
  • 0≤B[i]≤1090 \le B[i] \le 10^9
  • 1≤K≤1091 \le K \le 10^9
  • 답은 최대 101810^{18} 까지 커질 수 있으므로 64비트 정수를 쓰세요.

기대 복잡도

시간
O(N log(answer))
공간
O(1)

입출력 예

ABK기대 출력
[3][0]512
[2,3][0,0]54
[1,100][50,0]351

힌트

힌트

답을 직접 구하는 공식은 없지만, 시각 tt가 주어지면 그때까지 완성된 제품 수는 쉽게 셀 수 있습니다. ii번째 기계는 t≥B[i]t \ge B[i]일 때 ⌊(t−B[i])/A[i]⌋+1\lfloor (t - B[i]) / A[i] \rfloor + 1개를 완성합니다.

그리고 tt가 커질수록 완성 개수는 줄어들지 않습니다(단조성). 그러니 답 자체를 이분탐색할 수 있습니다.

주의할 점 두 가지입니다.

  • 탐색 상한은 2×10182 \times 10^{18} 정도로 넉넉히 잡으세요.
  • 개수의 합이 64비트도 넘칠 수 있습니다. KK에 도달하면 즉시 세기를 멈추세요.

복잡도 목표

제품을 하나씩 꺼내며 시뮬레이션하는 O(Klog⁡N)O(K \log N) 풀이는 KK가 최대일 때 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1000 ms도출됨

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.