[백준 문제풀이] 얼렁뚱땅 3079번 입국심사 풀이

https://www.acmicpc.net/problem/3079

 

# 구현으로 풀었을 때 : 시간초과

n, m = map(int,input().split())

array = []
for i in range(n) :
	num = int(input())
	array.append([num, 0])

for i in range(m) :
	temp = []
	for j in range(len(array)) :
		temp.append(array[j][1] + array[j][0])

	ind_ = temp.index(min(temp))
	array[ind_][1] = array[ind_][0] + array[ind_][1]


print(max(list(zip(*array))[1]))

# 이분탐색으로 풀었을 때 : 성공

n, m = map(int,input().split())

array = []
for i in range(n) :
	num = int(input())
	array.append(num)

start = 0
end = max(array) * m

temp = 0

while start <= end :
	mid = (start+end) // 2
	people = 0
	for ar in array :
		people += (mid // ar)

	if people >= m :
		end = mid - 1
		temp = mid

	else :
		start = mid + 1

print(temp)

근데 사실 진짜 구현으로만 풀고 어떻게 풀어야할지 몰라서 블로그 참고했다

이분탐색으로 푸는 거라고 아이디어 절대 혼자 머리에서 생각 못했는데

요즘 이분탐색 문제를 안풀어서 그런가 ? 혹시 다들 천재인가 ?