https://www.acmicpc.net/problem/13702
딱 봐도 이분탐색 문제인데, 왜 이분탐색 문제는 매번 풀 때마다 시원하게 풀리는 법이 없는가.
일단은 평범하게 start는 0, end은 막걸리 중 제일 많은 양으로 정해놓고 시작했다.
예전에 한 번 비슷한 문제를 풀다가 어리석게도 start를 입력 값 중 제일 작은 값으로 했다가 한참 헤맨적이 있었기 때문에 더 이상 속지 않는다. 아무도 속인적 없지만.
mid값은 당연히 start와 end의 중간 값으로 해주면서 이분 탐색을 수행했다. mid 값으로 막걸리를 나누어주었을 때 모두에게 나누어줄 수 있는지와 이전에 나누어준 용량보다 많은지를 체크해주며 갱신해나갔다. 나누어주는데 성공했을 때 막걸리가 나누어진 개수(?)와 사람의 수를 비교해서 사람 수보다 막걸리 잔 수가 더 나왔으면 더 많은 양으로 나누어줘도 된다는 의미이므로 start를 mid로 땡겨오고, 반대의 경우에는 end를 mid로 땡겨와준다.
처음에는 이렇게만 해놓고 제출했다. 그랬더니 틀렸단다. 스스로 반례를 떠올리지 못 할 것 같아서 질문에서 반례를 찾아보았다. 주어지는 막걸리의 양이 0인 경우를 생각하지 못했다. 그래서 잔을 나눌 때 0으로 나눠버려서 에러가 나는 것이었다. 또 1명에게 1만큼의 막걸리를 나누는 경우도 내 코드는 0이 나왔다. mid 값을 구할 때 (start + end) // 2로 한 것이 문제였다. 그래서 이 부분을 ceil 함수를 붙여 올림으로 바꿔주고 해결했다.
그런데도 통과가 안됐다. 마지막 반례로 1 1 / 2100000000 를 넣었는데 내 코드는 1575000001 따위의 이상한 결과를 내놓는 것이었다. 코드를 다시 살펴보니 새로운 start 값을 정해줄 때의 조건이 잘못되어있었다. 이 부분도 고쳐내니 잘 통과되었다..
이분탐색 문제는 정말 꼼꼼하게 생각해야하는 문제인 것 같다.. (킹받드라슈)
from math import ceil
from sys import stdin
n, k = map(int, stdin.readline().split())
mak = [0 for i in range(n)]
for i in range(n):
mak[i] = int(stdin.readline())
start = 0
end = max(mak)
result = 0
while start <= end:
mid = ceil((start + end) / 2)
count = 0
for i in range(n):
if mid != 0:
count += mak[i]//mid
if count >= k and result < mid:
result = mid
if count >= k:
start = mid + 1
else:
end = mid - 1
print(result)
해결에 도움을 준 반례들에게 이 영광을 돌립니다(?).
1 1
0
ans : 0
1 1
1
ans : 1
1 1
2100000000
ans : 2100000000