[python]백준 1654번: 랜선 자르기(이진탐색)

# 1654 랜선 자르기

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

1654번: 랜선 자르기

코드

K, N = map(int, input().split())
already = [int(input()) for _ in range(K)]
start, end = 1, max(already)

while start <= end:
    mid = (start + end) // 2 # 중간 위치
    line = 0
    for i in already:
        line += i // mid # 분할 된 랜선 수

    if line >= N:
        start = mid + 1
    else:
        end = mid - 1
print(end)

📝 풀이

주어진 랜선을 잘라서 필요한 랜선의 개수 N을 충족하는 동시에 자를때의 랜선의 길이가 max인 값을 찾아야한다.

이 문제를 딱 보자마자 while문을 통해서 값을 계속해서 찾아줘야겠네 라는 생각이 들었다.

하지만 생각보다 while문 안에 로직이 쉽게 구현되지 않았고, 구글형의 도움을 받았다.

🔓 정답 코드 뜯어보기

# K 가지고 있는 랜선의 갯수
# N 필요한 랜선 갯수
K, N = map(int, input().split())
already = [int(input()) for _ in range(K)]
start, end = 1, max(already)

while start <= end:
    mid = (start + end) // 2 # 중간 위치
    line = 0
    for i in already:
        line += i // mid # 분할 된 랜선 수

    # 랜선의 개수가 분기점
    if line >= N: # 랜선이 목표치 이상이면 mid + 1을 start로 두고 while반복
        start = mid + 1 
    else: # 랜선이 목표치 이하면 mid - 1을 end로 두고 while 반복
        end = mid - 1
print(end)

결국 핵심은 랜선의 길이를 움직여서 랜선의 개수를 채우면서 랜선의 최댓값을 찾는 것이다. 이때 1부터 무작정 찾는 것 보다는 시작과 끝의 중간값을 찾아서 탐색하는 것이 훨씬 효율적이다. 

 

따라서 가장 짧은 길이 1을 start로, 가장 긴 길이를 end로 둬서 이분탐색을 시작한다.

시작과 끝을 더해서 중간값 mid를 만들어주고 리스트에 담아놨던 랜선들을 for문으로 돌면서 길이를 중간값으로 나눈 몫을 line에 더해준다.

 

랜선(line)의 개수가 필요한 개수보다 많으면 mid +1을 start에 저장시키고 랜선의 개수가 목표치 이하라면 mid -1을 end에 저장시켜준다. 계속해서 while문을 돌면서 start와 end가 같아질때 결과값인 end를 출력하면 랜선 길이의 최댓값이 나오게 된다.