백준 - 1654 랜선 자르기

💡문제 분석 요약

• 랜선의 길이를 움직여 랜선 갯수를 확인하는 문제

💡알고리즘 설계

• start : 1 , end : 랜선 길이 중 가장 긴 길이
• mid 를 start 와 end의 중간으로 두고, 모든 랜선 값을 mid로 나눠 총 몇개의 랜선이 나오는지 확인
• 랜선이 목표 이상이면 start : mid + 1
• 랜선이 목표 이하이면 end : mid - 1
  (이분탐색)
• start == end라면 조건을 만족하는 최대의 랜선 길이를 찾는다.

💡코드

import sys
K, N = map(int, input().split())
lan = [int(sys.stdin.readline()) for _ in range(K)]
start, end = 1, max(lan) #이분탐색 처음과 끝위치

while start <= end: #적절한 랜선의 길이를 찾는 알고리즘
    mid = (start + end) // 2 #중간 위치
    lines = 0 #랜선 수
    for i in lan:
        lines += i // mid #분할 된 랜선 수
        
    if lines >= N: #랜선의 개수가 분기점
        start = mid + 1
    else:
        end = mid - 1
print(end)

💡시간복잡도

O(logN)

💡 틀린 이유

💡 틀린 부분 수정 or 다른 풀이

💡 느낀점 or 기억할정보

백트래킹이랑 dfs bfs 하다가 이진탐색 문제 나오니까 조금 쉬워진 느낌이다..
난 이진탐색도 중요하지만 그래프 탐색이 좀 더 어려우니 같이 공부 좀 해야겠다..