[BOJ] 1654. 랜선 자르기

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

1654번: 랜선 자르기

 

 

1. 해결방법

"""
1. 아이디어
- 이분 탐색을 이용한다.
- 이분 탐색이 끝날 때까지 while문을 돌린다.
- start는 1, end는 로프 길이가 가장 긴 숫자로 한다.
- 랜선의 길이가 타겟 이상이면 mid + 1, 이하면 -1
"""

 

 

2. 정답코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
nums = sorted([(int(input())) for _ in range(N)])

start, end = 1, max(nums)

while start <= end:
    mid = (start + end) // 2
    lines = 0

    for num in nums:
        lines += num // mid

    if lines < K:
        end = mid - 1
    else:
        start = mid + 1

print(end)

높지 않은 난이도임에도 불구하고 생각이 정지되었고, 아이디어가 딱히 떠오르지 않았다..일단 이분 탐색이라는 것을 파악하지 못하였고, 그에 따라 당연히 자를 랜선의 길이를 정하는 것 조차 하지는 못했다.