백준 1654 : 랜선 자르기 - 파이썬 : 이분탐색 활용

문제

문제 링크

랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다.
K줄에 걸쳐 가지고 있는 각 랜선의 길이가 정수로 입력
N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력

쉽게 말해 K개의 랜선을 최대 몇 센티미터로 잘라야 N개의 랜선을 만들 수 있는지를 구하는 문제다!!

해결 방안

이분탐색을 활용했다!

📢이분탐색이란?

출처

위에서 볼 수 있듯이 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다!!

이 문제에서는 front (low)를 1로 놓고 rear (high)를 랜선 중 가장 긴 랜선으로 했다.
그 후 위처럼 반씩 쪼개가며 범위를 좁히는 방식으로 구현했다 :D

코드

시간초과 코드

import sys

k, n = map(int,sys.stdin.readline().split())

lan = []

for i in range(k):
    lan.append(int(sys.stdin.readline()))

maximum = max(lan)

for i in range(maximum, 0, -1):
    cnt = 0
    flag = 0
    
    for j in range(k):
        cnt += lan[j] // i

        if cnt >= n:
            flag = 1
            break

    if flag == 1:
        break

print(i)

이렇게 2중 반복문을 도니 시간복잡도가 커져서 그런지 시간초과가 떴다ㅜㅠ

이분탐색 코드

import sys

k, n = map(int,sys.stdin.readline().split())

lan = []

for i in range(k):
    lan.append(int(sys.stdin.readline()))

front = 1
rear = max(lan)

while front <= rear:
    mid = (front + rear) // 2
    cnt = 0

    for i in range(k):
        cnt += lan[i] // mid

    if cnt >= n:
        front = mid + 1
    else:
        rear = mid - 1

print(rear)

결국 이분탐색을 활용해서 풀었다ㅎㅎ

쉽게 풀지는 못했지만 그래도 풀어서 참 좋았다:D
점점 고수가 되어가는 느낌이군요（＾∀＾●）ﾉｼ