[#1654] 랜선 자르기

문제

#1654 랜선 자르기
Silver2
적용 알고리즘: 이분 탐색 알고리즘

---

풀이 방법

• n의 범위는 1부터 1000000까지 가능하므로 이분 탐색으로 절반씩 줄여 가며 탐색한다.
• N개보다 많이 만드는 것도 N개를 만드는 것에 포함이 된다.
• 입력된 랜선의 길이중 최댓값보다 더 큰 길이로 자를 순 없으므로 길이 탐색의 범위를 1에서 랜선 길이의 최댓값으로 설정한다.(low = 1, high = max(랜선))
• 특정 랜선에 길이가 i인 랜선이 몇개 들어가는지 알기 위해선 몫 연산자를 사용하면 된다.

코드 흐름

1. 입력을 받는다.
2. 이분탐색의 범위를 1~max(랜선)으로 잡는다.
3. 반복문으로 이분탐색을 진행한다. 입력받은 모든 랜선에 대해서 현재의 mid(랜선 길이)로 나누었을 때의 총 합(total)을 저장한다.
4. 만일 total 값이 더 많이 나온 경우 나누는 랜선의 길이를 증가해도 되므로 mid를 증가한다.
5. total값이 더 적다면 mid를 감소한다.
6. low와 high가 교차하여 반복문을 중단할 때가지 3~5과정을 반복하고, high를 출력한다.

코드

k, n = map(int, input().split())
line = []
for i in range(k):
    line.append(int(input()))

low = 1
high = max(line)

while (low <= high):
    mid = (low + high) // 2
    total = 0
    for i in range(k):
        total += line[i] // mid
    
    if (total >= n):
        low = mid + 1
    else:
        high = mid - 1

print(high)

체감 난이도: 4/5
지난번에 비슷한 유형의 2805번 문제를 한번 풀어봐서 이번 문제는 쉽게 풀 수 있었다. 만일 어떤 변수에 대해 이분탐색을 진행할 지 모르겠다면 문제의 조건에서 범위가 넓은 변수를 우선 생각하여 문제를 해결해도 괜찮을 것 같다.