📌 문제 탐색하기
👉 문제바로가기
K: 이미 가지고 있는 랜선의 갯수(1<=K<=10,000)
N: 필요한 랜선의 갯수(1<=N<=1,000,000)
K개의 랜선으로 N개의 랜선을 만들어야 합니다. 이 때 최대한 긴 길이로 N개의 랜선을 만들 수 있도록 해야하고, 그 길이를 구하는 것이 목표입니다. N개보다 많은 랜선을 만들 수 있는 경우도 N개를 만드는 것에 포함된다는 조건에 유의해야 합니다.
보통의 이분 탐색처럼 mid를 구하고, 이 값으로 만들 수 있는 랜선의 개수를 구합니다.
- 랜선의 개수가 N보다 작은 경우 더 짧은 랜선으로 탐색해야합니다.
- 랜선의 갯수가 N이 되거나 N보다 큰 경우 검색을 바로 종료하지 않고 더 긴 길이의 랜선으로도 랜선의 갯수가 N을 만족하도록 할 수 있는지 탐색해야 합니다.
📌 알고리즘 선택
1. O(N)
예제 입력과 출력을 예로 들어봅시다. 802, 743, 457, 539의 길이가 주어진 경우 여기서 가장 작은 길이는 457입니다. 따라서 457보다 N의 길이가 길면 항상 K<=N인 조건을 만족할 수 없으므로 가능한 길이는 1부터 457까지입니다. 457부터 시작하여 1까지 가장 긴 길이부터 하나씩 대입하여 11개의 랜선이 만들어지는지 확인하는 경우를 생각할 수 있을 것입니다. 하지만 이 경우 2^31개의 연산이 필요하고, 시간제한 2초 안에 불가능합니다. N이 우리가 원하는 값인 11이 나왔음에도 불구하고 반복문을 계속 돌면서 랜선의 길이를 구할 것이므로 효율적인 방법도 아닙니다.
2. O(logN)
logN으로 탐색하면 약 31개의 연산이 필요하고, 시간제한 2초 안에 가능합니다. 최대한 필요한 부분 위주로 탐색하기 위해 O(logN)의 시간복잡도를 가진 이진 탐색을 활용해봅시다.
📌 코드 설계하기
- K, N을 Input받고, K의 갯수에 해당되는 만큼 한 줄에 하나씩 랜선 길이를 입력받아 배열에 저장합니다.
- 탐색해야 할 최소, 최대 길이를 설정합니다.
- 랜선의 최대 길이를 출력합니다.
📌 시도 회차 수정사항
런타임 에러
import sys
K, N = map(int, sys.stdin.readline().split())
len_arr = [int(sys.stdin.readline()) for _ in range(K)]
arrN = []
def max_search(arr1, N, start, end):
while start <= end:
mid = (start + end) // 2
count = 0
for i in range(K):
count += arr1[i] // mid
if count > N:
start = mid + 1
elif count < N:
end = mid - 1
elif count == N:
start = mid + 1
arrN.append(mid)
return max(arrN)
result = max_search(len_arr, N, 1, max(len_arr))
print(result)max_search함수에서 arrN이 비어있는 경우 max(arrN)을 리턴할 수 없어 런타임 에러가 발생할 수 있습니다. 위 코드의 경우 랜선이 N개가 나오지 않으면 N을 1씩 증가시키면서 배열을 생성해야 합니다.
위 코드는 문제에서 "N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다."라는 조건을 만족하지 않기 때문에 맞지 않은 코드입니다.
시간초과
import sys
K, N = map(int, sys.stdin.readline().split())
len_arr = [int(sys.stdin.readline()) for _ in range(K)]
arrN = []
def max_search(arr1, N, start, end):
while start <= end:
mid = (start + end) // 2
count = 0
for i in range(K):
count += arr1[i] // mid
if count > N:
start = mid + 1
elif count < N:
end = mid - 1
else: # count == N
start = mid + 1
arrN.append(mid)
if arrN == []:
N += 1
max_search(len_arr, N, 1, max(len_arr))
return max(arrN)
result = max_search(len_arr, N, 1, max(len_arr))
print(result)재귀함수의 사용으로인해 시간초과가 발생했다.
📌 정답 코드
import sys
K, N = map(int, sys.stdin.readline().split())
len_arr = [int(sys.stdin.readline()) for _ in range(K)]
result = 0
#탐색
#start, end: 탐색해야 할 최소, 최대 길이
def max_search(arr1, N, start, end):
while start <= end:
mid = (start + end) // 2
count = 0
for i in range(K):
count += arr1[i] // mid
if count >= N:
result = mid #더 긴길이를 탐색하기 전에 결과를 저장
start = mid + 1
elif count < N:
end = mid - 1
return result
answer = max_search(len_arr, N, 1, max(len_arr))
print(answer)
