알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/1654
소스 코드(파이썬)
import sys
input = sys.stdin.readline
K, N = map(int, input().split())
lan = [int(input()) for _ in range(K)]
end = max(lan)
def lan_length(n):
count = 0
for item in lan:
count += item // n
return count
def binarySearch(start, end, N):
if start > end:
return end
mid = (start + end) // 2
length = lan_length(mid)
if length >= N:
return binarySearch(mid+1, end, N)
else:
return binarySearch(start, mid-1, N)
print(binarySearch(1, end, N))풀이 요약
-
이분 탐색의 첫 범위 선택과, 주어진 랜선의 개수를 만족하는 "자를 길이" 중에서 가장 큰 값을 어떻게 구하는지가 핵심이다.
-
탐색할 "자를 길이"의 범위는 1부터, 가지고 있는 랜선의 길이 중 가장 긴 것 까지이다.
-
이분 탐색을 할 때, 만약 "자를 길이"로 가지고 있는 랜선을 잘라 만들 수 있는 개수가 N과 같다고 해서, 바로 그 개수를 리턴하면 안된다.
예를 들어
4 11
899
799
499
539
이 경우에는, 만약 length == N일 때 바로 그 때의 "자를 길이" mid를 리턴하도록 하면 218이 리턴된다.
하지만 219, 220, ..., 224도 조건을 만족하는 수이다.
이렇게 자른 총 개수가 N과 같음을 만족하는 "자를 길이"가 여러개인 경우가 있기 때문에, 이 중에서 최대를 리턴해줘야 함이 안되는 이유이다.
-
그래서, 조건문을
1번 : lengh(어떤 "자를 길이"로 자른 총 개수) >= N 인 경우와
2번 : 그 외 로 나눠준다.
그 이유를 알아보자.
우선 위 예제를 기용해서"자를 길이" : 218, 219, 220, 221, 222, 223, 224, 225, 226, 227 (mid)
"만든 개수" : 11, 11, 11, 11, 11, 11, 11, 12, 12, 12 (length)
이렇게 된다. 우선 mid = 218일 때, length = 11이므로 1번 조건문에 걸리게 된다.
start가 219로 설정되고 다시 재귀가 호출된다.
이런 식으로 오른쪽 방향으로 쭉 진행이 될 때, 가장 최후까지 진행되는 경우를 상정해보면,start가 최초로 length가 12가 되는 mid = 225 자리에 설정이 될 때, 이 때는 end 값이 상관없이
mid에 대한 length가 12 이상이 나오므로, start는 length가 11인 것 중 가장 큰 수인 224의 다음 수인 225가 최대로 될 수 있는 수이다.
한 편, 진행 중에 mid에 해당하는 length가 12가 됐다고 치면, 이 때는 2번 조건문에 걸려서 end가 min-1로 설정이 된다. 최후까지 진행된다고 하면, mid가 224가 되는 순간 length가 11이 되고, 이 때 1번 조건문으로 넘어간다. start 값에 상관없이 반드시 mid에 해당하는 length가 11 이하가 나오므로, end의 최소 가능한 수는 length가 11인 수 중 최대인 224이다.즉, 끝까지 진행하고나면 start = 225, end = 224로 교차되게 된다. 이 때 end를 리턴해주면 된다. 이게 length가 11이 되게하는 "자를 길이" 중 최대값이다.
배운 점, 어려웠던 점
-
처음에는 K <= N 이고, 랜선 중 가장 작은 길이를 end로 두면, end로 잘랐을 때 개수가 K개이고 이 것이 최대라서, end보다 작은 어떤 수로 잘라야 K개보다 많아져서 N개가 될 수 있다고 생각해서 범위를 min(lan)까지로 잡았는데, min(lan) 길이로 잘랐을 때 개수가 N보다 큰 경우가 있다는 것을 생각을 못했다.
-
length == N인 "자를 길이" mid는 여러 개인 경우가 있는데, 이 때 최대를 구하기 위해 그 때 재귀 단계에서의 mid에서부터 end까지 length가 1 늘어나는 경우를 찾고, 그 경우에는 늘어나기 직전의 mid를 리턴, 경우가 없다면 end를 리턴하는 방식으로 처음엔 작성했는데, 이 경우 만약 length == N인 어떤 "자를 길이"의 개수가 아주 많은 경우가 있어서 시간 초과가 나는 것 같다.
그래서, 다른 사람 풀이를 보고 조건문을 두 갈래로만 나누는, start와 end가 교차할 때의 end가 구하는 값이 되는 원리를 이해했다.
