[구현] 이름 (Lv.3)
걸린 시간
40분
접근 방식
제한사항이 1,000,000,000인 조건이 2개에 100,000인 조건이 1개 있다.
숫자가 매우 크므로 이분탐색을 노려야한다.
이분탐색을 쓰려면 판단 기준을 정해야하는데 그게 쉽지 않았다.
시간을 기준으로 이분탐색을 해야하는데 (정답이 시간이니까)
임의의 시간을 각 심사관의 소요시간으로 나눈 몫끼리 다 더하면 임의의 시간에 몇명 심사 가능한지 알 수 있다.
그 값이 n보다 큰지 작은지를 판단하면 된다.
예를 들어 25분이면 (25 // 7) + (25 // 10) = 3 + 2 = 5이므로 5명 심사 가능하다.
정답 코드
def solution(n, times):
answer = 0
left = min(times)
right = n*max(times)
while left <= right:
mid = (left+right)//2
res = 0
for time in times:
res += mid // time
if res >= n:
break
if res >= n:
answer = mid
right = mid-1
else:
left = mid+1
return answer배운점
이분탐색은 판단 기준이 의외로 쉽게 형성되니 생각을 단순하게 해야한다.
[구현] 서버 증설 횟수 (Lv.2)
걸린 시간
20분
접근 방식
단순하게 서버 증설할 타이밍에 증설할 만큼 지속시간에 맞춰 증설해주면 된다.
예를 들어 서버가 1개인데 지금 플레이어가 11명이라면?
(m은 3으로 가정한다)
총 5명까지는 서버를 증설 안해도 된다.
근데 11명이면 서버가 3개 필요하다.
12명이면? 서버가 4개 필요하다.
플레이어 수 : 0 1 2 3 4 5 6 7 8 9
필요한 서버 수 : 0 0 0 1 1 1 2 2 2 3
즉, 플레이어 수 // m 을 하면 필요한 서버 수가 된다.
정답 코드
def solution(players, m, k):
answer = 0
servers = [0 for _ in range(len(players))]
for i, player in enumerate(players):
if m * (servers[i]+1) <= player:
server_increase = ((player - (m * (servers[i]+1))) // m) + 1
answer += server_increase
for j in range(k):
if i + j >= len(players):
break
servers[i+j] += server_increase
return answer배운점
이상 미만, 초과 이하를 잘 분별해야한다.
