728x90
0. 문제 링크
https://www.acmicpc.net/problem/1654
1. 문제
2. 해결 알고리즘
이분 탐색
3. 이 문제의 특징
이 문제의 핵심은 최대 길이의 랜선으로 뽑는 것이다.
예를 들어서 603m의 랜선을 3개로 자른다고 했을 때 200m도 3개, 201m도 3개이다.
여기서 문제는 201m 200m 자른 결과 값이 똑같이 3개인데 어떻게 구분하냐는 것이다.
답은 right 값에 있다.
right 로 설정된 값은 이전 반복문에서 조건 값을 통과 하지 못한 (이분 탐색의 중간값) 바로 아래의 수이다.
그렇기에 만약 이번 반복문에서 통과가 되었다면, right 가 최대 값 일 것이다.
이 문제의 특징은 보통 (이분 탐색의 중간값)으로 비교하는 문제가 많은데 이 문제는 최대값이라는 조건 때문에
right 에 신경을 쓰지 못하고 이분탐색의 중간값으로 출력한다면 틀릴 것이다.
4. 코드
import sys
input = sys.stdin.readline
def main():
K, N = map(int, input().split())
arr = [int(input()) for _ in range(K)]
left = 1
right = max(arr)
mid = (left + right) // 2
while left <= right:
mid = (left + right) // 2
count = 0
for n in arr:
count += n // mid
if count >= N:
left = mid + 1
else:
right = mid - 1
print(right)
main()
728x90
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ 12015/파이썬]가장 긴 증가하는 부분 수열2 (0) | 2021.08.31 |
---|---|
[BOJ 1300 / 파이썬]K번째 수 (0) | 2021.08.31 |
[BOJ 1655 / 파이썬] 가운데를 말해요 (0) | 2021.08.26 |
[BOJ / 10217] KCM Travel 파이썬 (0) | 2021.08.20 |
[BOJ 12865/Kotlin] 평범한 배낭 (0) | 2021.02.14 |