[백준] 1197번 랜선 자르기

[백준] 1197번 랜선 자르기 - 파이썬

코딩 코딩 코오딩 2022. 4. 12. 09:15

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

import sys

k,n = map(int, sys.stdin.readline().split())
lan = []

for i in range(k):
    lan.append(int(sys.stdin.readline()))
lan.sort()

start = 1
end = lan[-1]

while start <= end:
    mid = (start+end)//2
    count = 0
    for i in range(len(lan)):
        count += lan[i]//mid

    if count >= n:
        start = mid + 1
    else:
        end = mid - 1

print(end)

이분 탐색의 대표적인 문제이다.

알고리금을 모르면 풀기 어려운 문제인 만큼 정답률이 높지는 않아

알고 있지 않으면 틀리는 문제라...

꼭 알아두고 기억해두자