문제를 보자마자 입력값의 범위가 너무 커서 시간복잡도를 고려해서 문제를 풀어야겠다는 생각을 했다.
우선 시간복잡도는 뒤로하고 문제에서 요구하는 답만 구해내는 것을 목적으로 코드를 작성하며 문제를 어떻게 해결 할지 생각해냈다.
내가 생각한 방법은 1부터 가진 랜선 길이의 최댓값까지 반복문을 돌면서 가진 잘라낼 수 있는 랜선의 개수를 센 뒤, 잘라낸 랜선의 수가 N 이상이면 잘라낸 길이를 비교하여 마지막에는 랜선을 N개 이상 잘라낼 수 있으면서 가장 긴 길이를 출력하도록 하는 것이었다.
결과적으로 이 논리로 문제를 해결하는 게 맞았다. 하지만 내가 처음으로 작성한 코드의 시간복잡도는 10000*(2^31-1)으로, 제한 시간인 2초를 한참 초과하였다. 초기 코드는 다음과 같다.
K,N=map(int, sys.stdin.readline().split())
have=[0]*K
for i in range(K):
have[i]=int(sys.stdin.readline())
temp_length=0
for i in range(1,max(have)):
count=0
for n in have:
count+=n//i
if count>=N:
temp_length=max(temp_length,i)
print(temp_length)사실 아무리 봐도 어떻게 문제를 해결해야 하는지 모르겠어서, 백준 문제 하단에 나와있는 알고리즘 분류를 확인해보았다.
결과적으로 이 문제를 해결하려면 '이분탐색' 알고리즘을 적용해야 했다. 이분탐색의 시간복잡도는 O(logN)으로 N의 값이 큰 경우에도 빠른 시간 안에 문제를 해결할 수 있다. 이코테 책에도 1000만 단위 이상을 다루는 문제라면 O(logN)의 속도가 필요한 경우가 많으므로, 탐색 범위가 2000만 정도를 넘어가면 이진탐색을 적용해보는 것이 좋다고 나와있다. 이 문제는 '전형적인' 이진탐색 문제라고 한다.
그렇다면 이진탐색을 적용해서 어떻게 이 문제를 해결할 수 있을까?
내가 알고있는 binary search 함수의 기본 형식은 다음과 같다.
def binary_search(array,target,start,end):
if start>end:
return
mid=(start+end)//2
if array[mid]==target:
return mid
elif array[mid]<target:
return binary_search(array,target,mid+1,end)
else: #array[mid]>target
return binary_search(array,target,start,mid-1)이 형식을 변형해서 본 문제를 해결하려면,
1) 내가 이분탐색으로 해결하려고 하는 문제(탐색 범위를 줄이려고 하는 부분)이 무엇인지 확실히 파악할 것.
2) 각 변수가 무엇을 의미하는지 확실히 이해할 것.
3) if문의 비교연산이 무엇을 의미하는지 확실히 이해할 것.
과 같은 단계를 거쳐야 했다. 나는 결국 위에 작성한 이분탐색 함수의 기본 형식에 얽매인채 2,3단계를 생각하지 않았고 결국 문제를 해결하지 못했다.
정답 코드를 먼저 보자.
import sys
def binary_search(have,min,max):
if min>max: #이분탐색 종료조건 설정
return max
mid=(min+max)//2
count=0
for n in have:
count+=n//mid
if count>=N:
return binary_search(have,mid+1,max)
else: #count<N
return binary_search(have,min,mid-1)
K,N=map(int, sys.stdin.readline().split())
have=[0]*K
for i in range(K):
have[i]=int(sys.stdin.readline())
print(binary_search(have,1,max(have)))이분탐색을 활용해서 아래 코드의 시간복잡도를 작게 만들어야 했는데, 갖고 있는 랜선에 대해서는 탐색 횟수를 줄일 수 없기 때문에 '최대 길이를 찾은 과정', 즉 range(1,max(have))이라는 범위를 줄여야 했다.
for i in range(1,max(have)):
count=0
for n in have:
count+=n//i
if count>=N:
temp_length=max(temp_length,i)이분탐색을 진행하기 위해서 보통 array, target, start, end의 네 가지 매개변수가 필요하지만, 이 문제에서는 특정 target 없이 1부터 max(have) 사이의 수를 탐색하며 count가 N 이상이 되게하는 수의 범위를 찾는 것이 목적이기 때문에 탐색 대상 array인 have, start, end의 세 가지 변수만 필요하다.
이때, 내가 이 문제를 해결하지 못한 이유는 start와 end가 의미하는 것이 무엇인지 정확히 짚고 넘어가지 않았기 때문이다.
여기서 start와 end는 각각 최소 길이와 최대 길이를 의미한다. 쉽게 말하자면, start와 end는 모두 잘라낼 랜선의 길이를 의미하고, 이때 이분탐색이 종료되고 나면 start~end는 count가 N 이상이 되는 범위로 변경되어 있을 것이다.
이때, 우리가 찾고자 하는 정답은 랜선의 '최대 길이'이기 때문에, 이분탐색이 종료되고 나서 return해야 하는 정답은 end값인 것이다. 코드를 다 작성하고 나서 직관적으로 이해하기 쉽도록 start는 min으로, end는 max로 이름을 변경해주었다.
if count>=N:
return binary_search(have,mid+1,max)
else: #count<N
return binary_search(have,min,mid-1)다음으로 이 if문의 비교연산 부분을 보면, count가 N 이상이면 탐색 범위를 mid+1~max로, N 이하면 min~mid-1로 조정한다. 이때 잘라낼 수 있는 랜선의 길이가 N보다 작다는 것은, 길이를 너무 길게 설정하여 N개만큼 랜선을 만들어내지 못한다는 것을 의미하므로, 범위를 하향조정해준다. 반면, 잘라낼 수 있는 랜선의 길이가 N 이상인 경우에는 길이를 더욱 늘려가면서 최대 길이를 찾아나갈 수 있도록 한다.
