[알각코] 인프런 4-2 랜선자르기 (결정알고리즘)

랜선자르기 (결정알고리즘)

문제 정보는 인프런의 파이썬 알고리즘 문제풀이 코딩테스트에 있습니다!

문제풀이

import sys
sys.stdin = open("input.txt", "r")
def count(len):
  cnt=0
  for x in line:
    cnt+= x//len
  return cnt

k, n = map(int, input().split())
line = []
res = 0
largest = 0

for i in range(k):
  tmp = int(input())
  line.append(tmp)
  largest = max(largest, tmp)

lt=1
rt=largest

while lt <=rt:
  mid = (lt+rt)//2
  if count(mid)>=n:
    res = mid
    lt=mid+1
  else:
    rt=mid-1

print(res)

sorting해서 첫 번째와 마지막을 계산해서 해당 범위 내에 2등분해서 접근하는 방식 m이 중간값이 a[mid]인데 이와 같으면 이 아이를 추출, m보다 크면 마지막 값을 가리키고있는 rt가 mid-1 번째로 범위를 좁히고, m보다 작으면 첫번쨰를 가리키고 있는 lt를 mid+1로 옮겨 범위를 좁혀 다시 반복한다.