백준 1654 Python

• 처음 문제를 보고 완전탐색 방법을 생각해냈지만 시간초과에 걸리고 말았다.
• 문제의 알고리즘 분류를 확인해 이분탐색 문제라는 것을 알았지만, 무엇을 기준으로 탐색의 범위를 좁혀 나갈지 이해가 되지 않았다.
• 구글링을 통해 완전탐색에서 생각했던 방법과 비슷하게 최소, 최대 랜선 길이를 기준으로 이분탐색하면 되었다.

1번 풀이

import sys
input = sys.stdin.readline

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

mean = sum(LAN) // K

while True:
    count = 0
    for i in range(len(LAN)):
        count += LAN[i] // mean

    if count != N:
        mean -= 1

    if count == N:
        print(mean)
        break

2번 풀이

import sys
input = sys.stdin.readline

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

# 랜선을 자를 기준 길이를 이분탐색 하자
low = 1
high = max(LAN)
answer = 0
while low <= high:
    count = 0
    middle = (low + high) // 2
    for i in range(K):
        count += LAN[i] // middle
    
    if count >= N:
        low = middle + 1
        # N개 이상 만들 수 있는 가장 큰 길이 값이어야 한다.
        answer = max(answer, middle)
    else:
        high = middle - 1

print(answer)

참고 사이트 https://cocoon1787.tistory.com/288