[백준] 1654번 : 랜선 자르기

문제

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

풀이

[백준] 1654 : 랜선 자르기 🥈(실버2)
🎯 정답률 :21.179%

• [알고리즘 : 이진 탐색(Binary Search)]

<✅ 문제 요약>

0. 랜선의 개수 K, 필요한 랜선의 개수 N
1. 랜선을 필요로 하는 만큼 잘라야한다.
2. 이미 자른 다른 랜선을 가져다 붙일 수 없다.
3. 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다.

<✅ 풀이방법 & 이진 탐색(Binary Search)으로 푼이유?>

1. 랜선은 합칠 수 없다.
2. 랜선을 나눌 수 있는 값을 가장 빠르게 탐색 할 수 있다. (시간복잡도 log(n))
3. start와 end 같이지면 멈추고 출력

코드(code)

import sys 
input = sys.stdin.readline
#K : 랜선의 개수, N: 필요한 랜선의 개수
K, N = map (int, input().split())
LanArr = [int(input()) for i in range(K)]
# 이진 탐색은 정렬이 되어있어야 한다.
LanArr.sort() 

start ,end =1, LanArr[K-1]
while start <= end:
    mid =  (start + end) //2
    lan_cnt = 0 # 랜선의 자르는 개수 총합

    for i in range(K):
        lan_cnt += LanArr[i]//mid
    	if lan_cnt >= N:
        	start = mid + 1
        elif lan_cnt < N:
            end = mid -1
    print(start,end)

# while문이 끝나고 나면 end 출력
print(end)

회고

이진탐색(Binary Search) 정말 빠르게 찾을 수 있다는 걸 느끼고,
코테 문제를 이진탐색으로 푼게 거의 없어서 알고리즘 이해가 올라간 느낌이다.
이진탐색 앞으로 나오면 잘 풀 수 있을듯 ?

• [해당 코드]

  https://github.com/joejames0830/ps_study/blob/main/Binary_Search/1654(%EB%9E%9C%EC%84%A0%20%EC%9E%90%EB%A5%B4%EA%B8%B0).py