문제링크: https://www.acmicpc.net/problem/2343
이진탐색 문제입니다. 이진탐색은 보통 리스트 탐색에서 활용되는 알고리즘인데, 반대로 경우를 탐색하는 문제가 종종 보여서 대표로 하나 가져왔습니다.
Problem
문제가 이해하기 조금 어렵습니다. 첫 줄에는 강의의 수와 담을 디스크의 수가 나옵니다. 그다음 줄에는, 강의의 크기가 리스트로 주어집니다. 주의할점은 문제에서 이 리스트의 순서를 바꾸면 안된다고 명시해놨습니다. 디스크의 갯수의 맞게 동영상을 끊어서 담아야한다고 할 때, 가장 큰 디스크 크기의 최솟값을 찾는 문제입니다.
주어진 예를 풀어서 설명하자면, 1 2 3 4 5 6 7 8 9 의 크기의 강의들을 총 3개의 디스크에 나눠 담아야 합니다. 가장 큰 디스크의 크기를 17 이라고 한다면, 1 ~ 5까지, 6~7 까지, 그리고 8~9 까지 이렇게 세개로 강의를 나눠 담을 수 있고, 이 값이 가장 큰 디스크가 가질 수 있는 크기의 최솟값입니다.
Approach & Solution
문제를 읽자마자 생각난 문제가 하나 있었는데, 백준 문제중 공유기 설치가 떠올랐고, 그 문제를 이진 탐색으로 푼다는 것이 생각났습니다. 그래서 이진 탐색으로 접근해 보았는데, 생각보다 구현하기 까다로워서 힌트의 힘을 조금 빌렸습니다..ㅎㅎ
풀이의 트리거는 '한 디스크의 크기를 이진탐색으로 찾자' 입니다. 디스크가 가질수 있는 최솟값을 start로, 최댓값을 end로 잡고 최적값을 이진탐색하는 겁니다.
n, m = map(int,input().split())
target = list(map(int,input().split()))
start = end = 0
for i in target:
if start < i:
start = i
end += i
while start <= end:
middle = (start + end) // 2
sum = 0
count = 0
for i in range(n):
if sum + target[i] > middle:
count += 1
sum = 0
sum += target[i]
if sum != 0:
count += 1
if count > m:
start = middle + 1
else:
end = middle - 1
print(start)코드를 쪼개서 살펴보겠습니다.
for i in target:
if start < i:
start = i
end += i우선, 최솟값과 최댓값을 start와 end에 설정하겠습니다.
while start <= end:
middle = (start + end) // 2
sum = 0
count = 0
for i in range(n):
if sum + target[i] > middle:
count += 1
sum = 0
sum += target[i]
if sum != 0:
count += 1
if count > m:
start = middle + 1
else:
end = middle - 1본격적인 이진탐색 루프입니다.
for i in range(n):
if sum + target[i] > middle:
count += 1
sum = 0
sum += target[i]먼저 sum에 강의를 순차적으로 더해주는데, 더한 값이 디스크에 안들어가면, count를 늘려주고 sum을 리셋합니다. 이렇게 middle크기의 디스크가 몇장이 필요한지 찾습니다.
if sum != 0:
count += 1마지막 디스크가 비어있는지, 차있는지 확인합니다.
if count > m:
start = middle + 1
else:
end = middle - 1마지막으로 start, end값을 결과에따라 조정합니다. 원래 원했던 갯수보다 더 많다면, 더 큰 단위의 디스크가 필요하므로 start를 올려주고, 반대일시 end를 내려주면 됩니다. count가 m과 일치할때 loop을 빠져나오게되고, 그때의 start값이 답이 되겠습니다.
Conclusion
저는 구현할때, 디스크의 갯수를 어떻게 확인해야 할지 감이 안오더라구요. 하지만, 큰 틀에서 이진 탐색을 어떻게 적용해야 할지는 바로 알아챘습니다. 그런 면에서는 쉬운문제라고 할 수 있겠군요. 시간이 되면 위에서 언급한 공유기문제도 풀어보면 좋을것 같습니다!
