이 문제는 이진탐색을 활용해서 풀 수 있었다.
문제와 알고리즘을 짜는 것 자체는 쉬웠다. 근데 제출만하면 자꾸 틀렸다고 떴었다. 그래서 high를 출력해보니까 값이 이상했다.
high 값을 가장 긴 길이로 놓아도 되지만, 어차피 이진탐색이니까 몇 번 더 계산하는 거 별 차이 없을테니 쉬프트 연산 한 번 써보자 하는 마음으로 2^31 - 1을 1 << 31 - 1로 표현했었다.
(쉬프트 연산: 왼쪽으로 n 칸 = 2^n배, 오른쪽으로 한 칸 = 2^-n배)
근데 이게 문제일줄야 🙂
콘솔에서 이걸 출력해보고 알았다.
>>> high = 2 ** 31 - 1
>>> high
2147483647
>>> high = 1 << 31 - 1
>>> high
1073741824그냥 high 값이 잘못된 거였다~ 연산자 우선순위를 잘 모르고 사용한 결과였다 😥
쉬프트 연산자가 +, - 보다 우선 순위가 낮아서 내가 원하는 값을 계산하기 위해서는 괄호를 쳐줘야했다.
high = (1 << 31) - 1 # 2 ** 31 - 1
high = 1 << 31 - 1 # 2 ** (31 - 1)정답 코드
import sys
K, N = map(int, sys.stdin.readline().split())
wires = []
for i in range(K):
wires.append(int(sys.stdin.readline()))
low = 1
high = (1 << 31) - 1
while low <= high:
mid = (low + high) // 2
cnt = 0
for wire in wires:
cnt += wire // mid
if cnt < N: # 개수가 모자를 경우 길이를 줄여야 함
high = mid - 1
else: # 모자르지 않으면 일단 저장하고 길이를 늘여서 검사
ans = mid
low = mid + 1
print(ans)