[Python 3] BOJ - 1654 "랜선 자르기"

 # 문제 링크 : https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 # 풀이 :

 개인적으로 문제의 핵심은 갯수를 기준으로 길이를 구하는것이 아니라 길이를 기준으로 갯수를 확인하는 것이다. 이는 이분 탐색을 하기 위함이다. 예를 들어 전체 랜선의 길이가 1, 2, 3, 4, 5라고 할 때, 일정한 길이의 랜선을 3개를 만들때, 가능한 길이의 범위는 1이상 5이하이다. 길이가 k인 랜선을 만들고자 할 때 만들어지는 랜선의 갯수는 각 원소를 k로 나눈 몫이 된다. 따라서, k의 범위에 따라 구해지는 랜선의 총 갯수는 다음과 같다

1) k = 1, lan = 15

2) k = 2, lan = 6

3) k = 3, lan = 3

4) k = 4, lan = 2

5) k = 5, lan = 1

 그러나, k을 1만큼만 움직인다면 시간제한을 피할 수 없다. 아래의 그림을 참고하자

<그림 1. 이분 탐색 전>

 현재 상황에서 최대와 최소의 절반 값인 now가 target보다 적다. 따라서 min과 now사이에 있는 모든 경우는 정답이 될 수 없다. 따라서 최소값을 옮겨줘야 한다. 마찬가지로 now도 범위에 들지 않기 때문에 min을 now + 1로 바꿔준다면 새로운 now는 이전의 값보다 target과 가까워질 것이다.

<그림 2. 이분 탐색 후>

 여전히 min과 now사이에 속해있는 경우는 답이 될 수 없지만, 그림 1과 비교하여 그림 2의 target과 now사이의 거리는 확연히 줄어들었음을 알 수 있다. 그림1, 2에서는 min을 움직이는 경우, 즉 target이 max쪽에 가까운 경우만 보였지만, 반대의 경우(target이 min쪽에 가까운 경우)는 max를 now - 1로 바꾸주면 된다. 만일 now가 target에 가까운 경우는 탐색을 종료하는 것이 아니라, 우리가 찾는 랜선의 갯수와 now가 같은것이지, 그때의 길이가 반드시 최대길이는 아님에 주의하여야 한다. 따라서 갯수가 같아도 min이나 max를 지속적으로 움직여주어야 한다.

 

 # 코드 

import sys

# 입력부
num, k = map(int, sys.stdin.readline().split())
lan = []
ans = 0
for i in range(num):
    temp = int(sys.stdin.readline())
    lan.append(temp)

# 이분 탐색을 하기 위해서는 반드시 정렬이 필요하다
lan.sort()

# check : 길이가 a일 때 k보다 많은 랜선이 잘리는지를 판별하는 함수
def check(a):
    cnt = 0
    for i in range(num):
        cnt += lan[i] // a
    return cnt >= k
    
# go : 이분탐색을 실행하는 함수
def go(left, right):
    global ans
    while left <= right:
        mid = (left + right) // 2
        if check(mid) == True:
        	# 이분탐색으로 k개를 찾더라도 최대값을 갱신한다
            if ans < mid:
                ans = mid
            left = mid + 1
        else:
            right = mid - 1

# 길이의 최소값은 1이며, 최대값은 원소의 최대값이다
go(1,lan[-1])
print(ans)