✔ 풀이를 위한 아이디어
- 이분탐색 (Binary Search) 의 활용
✔ 수정 전 코드
import sys
K, N = map(int, sys.stdin.readline().split())
ori_lan = [int(sys.stdin.readline()) for _ in range(K)]
answer = min(ori_lan)
count = 0
for i in range(answer, 0, -1):
for n in ori_lan:
count += int(n / i)
if count >= N:
break
else:
count = 0
print(i)- 기존에 가지고 있던 랜선을 잘라서 만드는 것이기 때문에, 구하려는 정답은 가지고 있던 랜선들 중 가장 작은 값보다 커질 수 없다고 생각했다.
- 그러나 기존에 가지고 있던 랜선 중 하나를 과감하게 버리고 나머지를 쪼개서 요구한 개수를 채울 수 있다면 반례가 되므로 위의 풀이는 틀렸다.
- 또한, 위의 풀이는 1씩 감소시키면서 찾기 때문에 효율적인 알고리즘이라고 할 수 없다. (아마 위의 반례를 수정했더라도 시간초과가 나왔을 것이다)
✔ 수정 후 코드
import sys
K, N = map(int, sys.stdin.readline().split())
ori_lan = [int(sys.stdin.readline()) for _ in range(K)]
start, end = 1, max(ori_lan)
while start <= end:
mid = (start + end) // 2
count = 0
for l in ori_lan:
count += (l // mid)
if count >= N:
start = mid + 1
else:
end = mid - 1
print(end)- 따라서 가능한 모든 값의 범위 안에서 이분탐색을 활용하여 최대의 값을 찾아내는 방식을 선택하였다.
- 수정 전의 코드는 O(n)의 시간복잡도를, 수정 후의 코드는 O(log2n)의 시간복잡도를 가지고 있으므로 훨씬 효율적인 코드라고 할 수 있다.
- 문제를 보고 어떤 알고리즘을 적용하는 것이 효율적일지 고민하는 습관을 기를 필요가 있어보인다.
✔ 관련 개념
- 이분탐색 알고리즘: https://satisfactoryplace.tistory.com/39
