[알고리즘 TIL] 1654. 랜선 자르기

문제

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

설명

문제를 어떻게 풀 수 있을지 기본적인 케이스부터 생각해보았다.

분명 반복문은 활용할텐데, 영식이의 랜선의 길이를 반복문에 대입하여 문제를 푸려고하니까 안풀렸다.

 

그래서 생각한 게 랜선의 길이를 1부터 영식이의 랜선의 길이 최댓값까지 반복문을 돌면서 영식이의 랜선에 대해 나누었을 때, K값과 동일하게 나누어 떨어지는 경우 정답이 출력되었다. 

 

하지만 이 방법은 완전 탐색 방법으로 시간이 너무 오래걸렸다.

따라서 내가 알고 있는 알고리즘 중에 어떤 것을 활용할 수 있을까 생각해보니, 이진 탐색을 활용하여 최댓값을 빠르게 구하면 되었다. 또한, 랜선의 길이가 2^31 - 1 인 것을 보고 이진 탐색이지 않을까 떠올렸다.

 

첫 시도에서는, 2%에서 틀림이 떴다. 원인을 파악하기 위해서 경계값인 N=1, K=1 Lans = [1,000,000] 을 입력하니 1,000,000이 아닌 750,000이 출력되었다. 내가 기존 이진탐색 함수를 외우다 보니 target 값이랑 동일하면 return 해버리기 때문이다. 750,000이 target 값이랑 동일해도, 더 큰 값이 정답일 수 있으니 bs(mid+1,end) 를 또 호출해줘야 한다.

 

두번째 시도에서는 12%에서 런타임 에러가 떴다. 질문 게시판에서 원인을 찾았는데, 꼭 target 값과 동일한 경우만 정답이 아니라, target 보다 큰 수여도 정답일 수 있기 때문이다. N=4, K=5, Lans = [10, 10, 10, 10] 인 경우, length=5 인 경우 총 갯수가 8개로 target 보다 크지만 정답이기 때문이다.

구현

possibleLengths = []

def binary_search(lans, maxLength, targetCount):
    def getCount(lans,length):
        cnt = 0
        for lan in lans:
            cnt += lan // length
        return cnt
    
    def bs(start,end):
        if start>end: return
        mid = (start + end) // 2
        cnt = getCount(lans,mid)
        if cnt == targetCount: 
            possibleLengths.append(mid)
            return bs(mid+1,end)
        if cnt > targetCount: 
            possibleLengths.append(mid)
            return bs(mid+1,end)
        if cnt < targetCount: return bs(start,mid-1)

    return bs(1,maxLength)

N,K = map(int,input().split(" "))
lans = []
maxLength = 0
for _ in range(N):
    length = int(input())
    if maxLength < length: maxLength = length 
    lans.append(length)

binary_search(lans,maxLength,K)
possibleLengths.sort()
print(possibleLengths[-1])

새로 알게된 점

실버 상위 문제쯤 되면, 누구나 문제를 어려워한다. 일단, 가장 기본적인 케이스부터 시도해보면서 문제를 파악해가고, 시간복잡도를 낮추기 위하여 내가 알고있는 알고리즘 중 어떤 것을 적용해볼 수 있을지 생각해보자.

 

또한 오류가 발생하면, 경계 케이스부터 대입해보며 원인을 파악해보자.