랜선자르기 (결정알고리즘)
문제 정보는 인프런의 파이썬 알고리즘 문제풀이 코딩테스트에 있습니다!
문제풀이
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로 옮겨 범위를 좁혀 다시 반복한다.