문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238#qna

접근법

조건을 만족하는 최소 시간을 구하는 문제이다. 해당 문제는 조건과 관계없이 최소 시간에서 최대 시간 사이 중 조건을 만족하는 최소 시간을 구하는 것으로 볼 수 있기 때문에 이분 탐색 문제라고 할 수 있다. 기본적으로 이분 탐색은 말 그대로 2개의 구역으로 나누기 때문에 여기서는 총 걸리는 시간을 기준으로 2개의 구역으로 나눌 수 있다. 그렇다면 최소와 최대를 먼저 설정하고 구역을 나눌 중간값을 설정한다.

min, max = 0, 10*18 # max는 문제에서 최대 사람과 한 명을 심사하는데 걸리는 최대 시간의 곱
mid = (min + max) // 2 # 여기서는 최소값을 구하기 위해 중간값이 항상 왼쪽에 치우치도록 이렇게 설정하지만 최대값을 구하는 문제라면 항상 오른쪽에 위치하도록 (min + max + 1) //2로 해야 함

다음은 조건식을 설정해야 한다. 이 문제에서는 각 심사관이 최대로 심사할 수 있는 사람의 수가 심사 받아야 할 사람의 수 이상인지를 확인한다.

def is_ok(n, times, max):
  sum = 0
  for time in times:
      sum += max//time

  return n <= sum

이제 조건문에 따라 탐색 범위를 좁혀나가야 한다. 만약 여기서 조건이 부합한다면, 최소 시간을 구하기 위해 최대 시간을 줄여나가야 한다. 그렇다면, 조건문에서 중간값을 최대치로 설정했을 때 조건을 만족한다면, 새로운 중간값을 설정하기 위해 전체 범위의 최대값을 중간값으로 바꾸고 다시 중간값을 설정한다.
만약 조건을 만족하지 못한다면, 전체 범위의 최소값을 중간값으로 변경해 범위를 좁혀 다시 탐색해야 한다.

if is_ok(n, times, mid):
	b = mid # 최대값을 구하는 문제라면 조건을 만족했을 때, 전체 범위의 최소값이 중간값이 돼야 하므로 a = mid가 되어야 함
else:
	a = mid + 1 # 마찬가지로 b = mid - 1

이 과정들을 전체 범위가 하나의 수를 가르킬 때까지 반복한다면, 이분 탐색은 완료된다. 모두 조합하면 다음과 같다.

def is_ok(n, times, max):
  sum = 0
  for time in times:
      sum += max//time

  return n <= sum
  
def solution(n, times):
  min, max = 0, 10*18
  while a < b:
      mid = (min + max) // 2

      if is_ok(n, times, mid):
          b = mid
      else:
          a = mid + 1

  return a # 또는 b

Reference

https://school.programmers.co.kr/questions/49151