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

문제

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

풀이

처음 문제를 접했을 때 어떤 방식으로 풀어야할 지 감이 잘 안 잡혀 알고리즘 분류를 봤습니다..

⁉️ 이분 탐색이네
어제 풀었던 알고리즘이니 기억을 복기시켜 문제를 해결했습니다.

• 제각각인 K개의 랜선을 이용해 N개 이상의 랜선을 만들자
• 자르고 남은 랜선은 버리자
• 이때 만들 수 있는 랜선의 최대 길이를 구하면 된다.

이 조건을 가지고 문제를 풀어봅시다.

이분 탐색을 활용하는 문제이니 시작점과 끝점을 설정해야 합니다.

l, r = 1, max(arr) # 랜선 길이의 최소값, 최대값

여기서 $l$값은 0으로 설정해야 되는 거 아니냐? 할 수 있습니다.
0으로 설정하게 되면 ZeroDivisionError가 발생할 수 있습니다.
만약 $l$값이 0, $r$값도 0일 때 중간값을 구하게 되면 중간값이 0이 나오게 됩니다.
이 0 값을 이용해서 연산을 하게 되면 에러가 발생하게 되는 겁니다.
(애초에 문제에 자연수라고 적혀있지만요)

이제 이분 탐색을 실시해봅시다.

while l <= r:
    mid = (l + r) // 2 # 중간값
    cnt = 0 # 랜선의 개수

왜 cnt를 선언해요?
N개 이상의 랜선을 만들어야 하기 때문에 개수를 확인해야 되기 때문이죠

for i in arr: # 입력된 K개의 랜선
        cnt += i // mid # 각 랜선을 길이 mid로 나누어서 총 개수에 포함
    if cnt >= n: # N개 이상이면
        l = mid + 1 # 최소 길이를 중간값 +1로 설정
    else: # N개 미만이라면
        r = mid - 1 # 최대 길이를 중간값 -1로 설정

이제 선언된 중간값을 이용해 K개의 랜선을 나누어 줍니다.
N개 이상이라면 $l$값을 증가시킵니다.

왜 $l$값을 증가 시켜요?
이 조건이 참이라는 것은 현재의 mid 길이로 나누었을 때 N개 이상의 랜선을 만들 수 있다는 것입니다.
하지만 이 이상의 길이에서도 N개 이상의 랜선을 만들 수 있는지 검사해야 되기 때문에 최소 길이를 늘려주는 것이죠

마무리로 랜선의 최대 길이인 $r$을 출력해주면 됩니다.

정답 코드

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
arr = [int(input()) for _ in range(k)]
l, r = 1, max(arr)

while l <= r:
    mid = (l + r) // 2
    cnt = 0
    for i in arr:
        cnt += i // mid
    if cnt >= n:
        l = mid + 1
    else:
        r = mid - 1
print(r)