2022.02.24 [백준] (python 파이썬) 랜선 자르기

 

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

1654번: 랜선 자르기

 

---

풀이

이 문제는 하나하나 모두 확인하면서 정답을 찾으면 시간초과를 피할 수 없다. 그래서 이분탐색을 이용해서 탐색시간을 줄였다. 우선 시작점은 가장 짧게 자를 길이인 1로 설정하고, end는 전체 랜선의 합을 n개로 나눈 값으로 설정했다.

이렇게 설정한 이유는 문제에서 남은 랜선은 다시 사용할 수 없다고 했기 때문에 전체를 하나로 만들고 n개로 나눈 값보다 항상 짧을 것이기 때문이다.

이렇게하면 탐색범위를 줄여 시간을 단축시킬 수 있다.

그래서 cnt이 n보다 작으면 더 작게 잘라주어야 하기 때문에 end=mid-1을 해주고 cnt이 n보다 크거나 같으면 해당 mid값을 ans에 저장하고 더 최적의 답을 찾기위해 start를 mid+1로 설정해주고 더 크게 자른 경우를 계산한다. 

그래서 이분탐색이 끝나면 ans에 최적의 길이가 저장된다.

k,n=map(int,input().split())
arr=[]
for _ in range(k):
    arr.append(int(input()))
 
start=1
end=sum(arr)//n
 
while start<=end:
    mid=(start+end)//2
    cnt=0
    for i in arr:
        cnt+=i//mid
    if cnt<n:
        end=mid-1
    else:
        start=mid+1
        ans=mid
 
print(ans)