치킨 튀기기[제로베이스]

철수는 개발자에서 은퇴하여 치킨집을 하게 되었다. 철수는 뛰어난 개발 실력으로 N대의 자동 튀김기를 만들어냈다.  i번째 자동 튀김기는 치킨을 한번 튀기는 데에 fry[i] 만큼의 시간이 걸리며, 튀김이 한 번 끝나면 clean[i] 만큼의 시간동안 자동 세척을 한다.

철수가 C번 치킨을 튀겨내려고 할 때, 최소한 몇 시간 동안 자동 튀김기를 가동해야 하는지 계산하시오.

제약사항
* 0 < N <= 100000
* fry[i]는 0 < fry[i] <= 100를 만족하는 정수
* clean[i]는 0 < clean[i] <= 100를 만족하는 정수
* 0 < C <= 100000
입출력 예

N = 2 
fry = [3, 6]
clean = [2, 1]
C = 20
answer = 58

N = 4
fry = [2, 2, 1, 3]
clean = [2, 4, 3, 2]
answer = 2

 

틀린 접근 방식

def solution(N, fry, clean, C) :
  total = []
  for i in range(len(fry)) :
    total.append([fry[i], clean[i], 0])
  total.sort(key=lambda x : (x[0] + x[1], x[0]))
  
  flag = True
  minute = 0
  while (C != 0) :
    for i in range(len(total)) :
      fry, clean, next_run = total[i]
      if next_run == minute :
        total[i][2] = next_run + fry + clean
        C -= 1
        if C == 0 :
          minute += fry
          flag = False
    if flag :
      minute += 1
  
  return minute

 

예제에 대한 정답은 나온다. 하지만 탐색 범위가 넓어 졌을때에 대한 고려가 되어있지 않다고 하여 점수가 절반이 되었다.

 

넓은 범위를 탐색해야 할때는 logN의 시간복잡도를 가진 이분 탐색으로 접근을 하자!!!

 

시간의 최댓값은 소요 시간이 가장 오래 걸리는 튀김기로만 튀겼을때 이다.

정답은 이 시간의 최댓값과 0 사이에 있을 수 밖에 없다

 

접근 방법: 

* 이진 탐색 방법으로 접근

def solution(N, fry, clean, C) :
  left = 0
  right = C * max([x + y for x,y in zip(fry, clean)])
  answer = right

  while left <= right :
    mid = (left + right) // 2
    
    val = 0
    for f,c in zip(fry, clean) :
      val += (mid + c) // (f + c)
    
    if val >= C :
      right = mid - 1
      answer = min(answer, mid)
    else :
      left = mid + 1


  return answer

print(solution(2, [3, 6], [2, 1], 20)) # 58
print(solution(4, [2, 2, 1, 3], [2, 4, 3, 2], 2))  # 2