[백준] 1654번: 랜선 자르기 - 파이썬

🧩문제 해석

갖고 랜선들을 k개의 같은 길이의 랜선으로 자르되, 자른 랜선쪼가리들은 다시 사용할 수 없다. 이때 만들 수 있는 최대 길이의 랜선을 구하는 문제이다.

 

📕 풀이

숫자 범위가 심상치 않다. 갖고 있는 랜선의 수가 백만개이고, 랜선이 길이는 2^31-1 보다 작은 자연수이다.ㅎ
일반적으로 접근했다가는 시간초과날 것이 분명하다. 이 문제는 이분탐색으로 풀어야 한다.

 

첫번째 아이디어!

• 가지고 있는 랜선중 최소값을 찾는다.
• 최소값 랜선을 end 값에 두고 이분탐색을 한다.
• 탐색 값들을 리스트에 저장하고, 최종적으로 그 리스트의 최대값을 출력한다.

 

최소값랜선을 end 값에 둔 이유는 최대값랜선을 end 값에 둔다 하여도 결국에는 최소값랜선에 올 것이라고 생각했다.

물론 맞는 말이긴 하다. 그러나 생각하지 못했던 반례가 있었다. 

바로 k의 값이다. k는 만들고자 하는 랜선의 갯수다. 만약 k가 1이라면, 랜선을 자를 필요가 없고, 가지고 있는 것들중에서 가장 긴 랜선을 사용하면 된다!

그래서 최소값랜선을 사용하면 위와 같은 경우의 처리가 어려워진다.

 

 

두번째 아이디어!

• 가지고 있는 랜선중 최대값을 찾는다.
• 최대값 랜선을 end 값에 두고 이분탐색을 한다.
• 탐색 값들을 리스트에 저장하고, 최종적으로 그 리스트의 최대값을 출력한다.

 

앞선 문제가 해결되었다!

 

💻 코드

n, k = map(int, input().split())
# 랜선의 길이 담은 리스트
lan = [int(input()) for i in range(n)]
# 갖고 있는 랜선중 최대값
max_lan = max(lan)
# 후보군 담을 리스트
res = []

def binary(k, start, end):
	# 이분탐색 시작
    while start <= end:
        mid = (start + end) // 2
        cnt = 0
        for i in lan:
        	# 구해진 값으로 랜선을 잘라본다
            cnt += i//mid
        # 자른 랜선들이 k 보다 작다면 좀더 작게 잘라야함
        if cnt < k: 
        	end = mid - 1
        # 조건을 만족하는 경우.
        else:
        	# 후보에 넣고 좀더 크게 만들어봄
            res.append(mid)
            start = mid + 1
# 이분탐색 함수 호출
binary(k,1,max_lan)
# 후보군에서 최대값 출력
print(max(res))

 

🔗 문제링크 : 랜선 자르기

1654번: 랜선 자르기