[이분탐색/백준] 1654번: 랜선 자르기

- 문제 : https://www.acmicpc.net/problem/1654

 

Silver Lv2 문제이고, 스스로 푼 문제다!

알고리즘 수업 때 들은 내용이 어렴풋이 기억나서 적용했다. 

 

풀이 과정 

 

• 각 랜선의 길이의 길이를 합한 다음 목표 갯수로 나누어서 원하는 결과를 만들기 위한 최대 길이를 구한다.
• 그 길이를 가장 끝점 이라고 정한뒤 이분탐색을 진행한다.
  • 각 단계에서 랜선을 얼마나 자를지 길이를 mid로 정한다. 
  • 각 랜선을 mid로 자른뒤 나오는 총 갯수를 result에 저장한다. 
  • result가 k 이상이라면, result로 만들 수 있는 총 갯수를 answer에 누적해간다.(문제에서 k개 이상 만들 수 있는 경우는 모두 정답으로 친다고 했다)
  • result가 k 초과라면 mid의 크기가 너무 커서 만들어지는 랜선의 갯수가 적은 것이므로 right를 줄여준다. 
  • answer에는 k개를 만들 수 있는 랜선의 길이들이 있으므로, 그 중에서 최댓값을 출력한다. 

 

- 정답 풀이 : 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
wires = [int(input()) for _ in range(n)]

answer = [] 
left, right = 0, sum(wires) // k 
while left <= right : 
    mid = (left + right + 1) // 2
    result = 0
    for wire in wires:
        result += wire // mid
    
    if result >= k:
        answer.append(mid)
        left = mid + 1
    else:
        right = mid - 1

print(max(answer))

 

신기하게 Pypy3로 돌릴 때보다 Python으로 돌렸을 때 시간이 더 짧다