728x90
반응형
문제 출처:
문제 풀이:
- 나무 자르기 문제와 매우 흡사한 문제이다. 이진탐색으로 풀면 가능하다
- 이 문제에서는 target이 잘라야 하는 랜선 길이라고 두고 매번 갯수를 파악하면서 n개를 기준으로 right,left를 조정하면된다.
k,n = map(int,input().split())
lans = []
for _ in range(k):
lans.append(int(input()))
left = 1
right = max(lans)
max_val = 0
while(left<=right):
mid = (left+right)//2
len_lans = 0
for i in lans:
len_lans += i//mid
if(len_lans>=n):
left = mid+1
if(mid >max_val):
max_val = mid
else:
right = mid-1
print(max_val)
반응형
'Computer Science > Algorithm' 카테고리의 다른 글
[백준] 2512 - 예산 (Python) (0) | 2021.04.09 |
---|---|
[백준] 최대,최소 힙 (Python) (0) | 2021.04.09 |
[백준] 2805 - 나무 자르기(Python) (0) | 2021.04.02 |
[백준] 2869 - 달팽이는 올라가고 싶다 (Python) (0) | 2021.04.02 |
[백준] 2529 - 부등호 (Python) (0) | 2021.04.02 |