백준 1654: 랜선자르기 해설- python

✏️ 문제

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

1654번: 랜선 자르기

 

✏️ 풀이

이진탐색을 이용하는 문제다. 이진탐색에 대한 내용은 여기에서

 

랜선의 길이에 대해서 이진탐색을 시행한다. 

k,n= map(int, input().split())
line = []
for _ in range(k):
    line.append(int(input()))
start = 1
end = max(line)
 
while(start<=end):
    mid = (start+end)//2
    cnt=sum([x//mid for x in line])

    if cnt>=n:
      start=mid+1 # 자른개수가 많으면 더 크게 잘라야함
    else:
      end=mid-1

print(end)

 

• k(가진 랜선 개수), n(필요한 랜선개수) 입력받기
• 가진 랜선의 길이를 입력받아 리스트에 저장
• 랜선길이가 최소 1은 되어야하니 start=1, 최대길이는 가지고 있는 랜선중 가장 긴 길이를 최대길이로 설정
• while(start<=end):
• 이진탐색을 위해 중간값((최소랜선길이+최대랜선길이)//2) 선언
• 중간값으로 가진 가지고 있는 랜선들을 다 잘라보고 랜선이 몇개생기는지 카운트한다.
• 만약 만들어야하는 랜선과 같거나 더 많은 양이 만들어 졌다면 최소랜선길이는 그 중간값+1이 된다.
• 하지만 반대로 양이 부족하다면 랜선의 최대길이는 그 중간값보다 작아야한다.
• 이를 start<=end인 지점까지 반복하다가 반복문을 벗어나면 최대길이 end를 출력한다.