[백준] 1654번 랜선 자르기 파이썬 풀이

1654번: 랜선 자르기

[문제]

---

[코드]

import sys
input = sys.stdin.readline

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

start = 1
end = max(LAN_LIST)

while start <= end:
    mid = (start + end) //2
    total = sum(f // mid for f in LAN_LIST)

    if total >= n:
        result = mid
        start = mid + 1
    else:
        end = mid - 1


print(result)

---

[풀이]

전형적인 이분 탐색 문제로 현재 정답률이 21.1%가 나오고 있는데 

솔직히 말해서 이분 탐색 문제중에서 어려운 문제는 아님..

난이도 : 5점 만점이 2.5? (실- 실버2 , 체감- 실버3.5?)

 

이분 탐색 문제를 풀어온 사람이라면 가볍게 접근해서 풀 수 있는 문제....

이분탐색 진행과정 - 이해를 위해서

 

문제의 핵심 

(1) 기준으로 잡은 길이로 랜선들을 잘랐을 경우 만들 수 있는 랜선의 갯수

(2) 이를 이분 탐색을 적용하여 최적의 길이를 찾아내기

 

import sys
input = sys.stdin.readline

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

이부분은 간단한 구현  ➡️ 현재 갖고 있는 랜선의 수 = k, 이를 잘라서 만들 필요가 있는 랜선의 갯수 = n으로 받는다

그리고 LAN_LIST라는 리스트를 형성하여 현재 보유한 랜선들의 길이를 추가해준다

 

start = 1
end = max(LAN_LIST)

while start <= end:
    mid = (start + end) //2
    total = sum(f // mid for f in LAN_LIST)

    if total >= n:
        result = mid
        start = mid + 1
    else:
        end = mid - 1


print(result)

핵심 로직

먼저 start와 end를 정해준다 

start는 1, end는 LAN_LIST의 최댓값으로 지정해준다 (end의 크기를 더 높게 줘도 상관없음, 어차피 첫 턴에 반 짤려 나가기 때문에)

 

이제 이분 탐색 알고리즘의 전형적인 단계인 while을 활용 start 가 end 보다 커질때 까지 반복한다

while 문 안에서 먼저 mid 값을 지정해준다. 

이는 start와 end를 합한 것을 2로 나눈 값으로 start 와 end의 중간값에 해당한다

그리고 total이라는 변수는 LAN_LIST에 들어 있는 LAN선을 mid로 잘랐을 때 만들 수 있는 랜선의 총합이다

즉, 우리가 만족하고자 하는 n(필요한 랜선의 갯수)와 비교할 값이다

 

만약 total의 수가 n 보다 같거나 크다면, 즉, 우리가 현재 기준(mid)으로 잘라서 만든 랜선의 갯수가 필요한 것과 같거나 크다면 start의 기준을 mid-1로 지정해준다.

왜냐하면 우리가 원하는 값은 현재 mid 왼쪽에 존재하고 있기 때문에

 

반면, toal의 수가 n 보다 작다면, 즉, 우리가 현재 기준(mid)으로 잘라서 만든 랜선의 갯수가 필요한 것보다 부족하다면 end의 기준을 mid + 1로 지정해준다

이는 우리가 원하는 값이 현재의 mid의 오른쪽에 존재하고 있기 때문이다

 

그리고 여기서 핵심은 total >= n일때 mid값을 result로 지정해주는 것이다 만약 start가 end보다 커지게 된다면 

그 이전의 while 문이 멈추고 start값을 갱신해주기 전 mid값이 정답이기 때문이다

 

따라서 마지막에 while문이 끝나고 result로 저장된 mid값을 출력하면 우리가 원하는 값이 나온다