백준 1654 랜선 자르기 Python 3

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

1654번: 랜선 자르기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1654.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys

def get_length(K, N, lans):
    left = 1
    right = max(lans)
    answer = 0
    while left <= right:
        mid = (left+right)//2
        cnt = 0
        for lan in lans:
            cnt += (lan//mid)
        if cnt >= N:
            answer = mid
            left = mid+1
        else:
            right = mid-1
    return answer

input = sys.stdin.readline
K, N = map(int, input().split())
lans = list()
for _ in range(K):
    lans.append(int(input()))
print(get_length(K, N, lans))

---

풀이 과정

풀이 시간 10분

길이가 각각 다른 K개의 랜선을 잘라서 N개의 길이가 같은 랜선을 만들 때 그 길이가 최대인 경우를 찾는 문제이다.

따라서, 자를 랜선의 길이를 기준으로 이분 탐색 알고리즘을 적용할 수 있다.

import sys

def get_length(K, N, lans):
	#자를 랜선의 길이의 범위 초기화 -> 랜선의 길이는 1부터 K개의 랜선 중 가장 길이가 긴 랜선의 길이만큼 자를 수 있다
    left = 1
    right = max(lans)
    answer = 0
    
    #이분 탐색
    while left <= right:
    	#자를 랜선의 길이를 mid로 가정
        mid = (left+right)//2
        #mid 길이의 랜선의 개수 카운트
        cnt = 0
        
        #K개의 랜선을 mid 길이로 자른다
        for lan in lans:
            cnt += (lan//mid)
            
        #mid 길이의 랜선이 N개 이상인 경우,
        if cnt >= N:
        	#mid를 answer로 갱신한다
            answer = mid
            #더 긴 길이로 자를 수 있을지 탐색하기 위해 left 범위를 늘린다
            left = mid+1
            
        #mid 길이의 랜선이 N개 미만인 경우,
        else:
        	#mid보다 자를 길이가 작아야하므로 right 범위를 줄인다
            right = mid-1
    return answer

input = sys.stdin.readline
K, N = map(int, input().split())
lans = list()
for _ in range(K):
    lans.append(int(input()))
print(get_length(K, N, lans))

#시간복잡도 = O(log n), 공간복잡도 = O(n)