💡문제 분석 요약
- N명의 사람들이 심사관들에게 심사를 받는 최소 시간을 구해야한다.
- 심사관마다 심사를 보는 시간은 제각기 다르다.
- 이때 주의할 점은, 당장 내가 심사를 받을 수 있는 상황이더라도 잠시 기다렸다가 심사를 더 짧게 보는 사람에게 가는 것이 이득일 수 있다는 것이다. ex) 당장 가서 100분 심사받기 vs 1분 기다렸다가 20분 심사받기
💡알고리즘 설계
- 잠시 기다리는 대기시간을 고려한다는 점에서 DP로 풀 수 있다고 생각했지만, 입력 값이 10억인 것을 보고 안되는 것으로 판단했다...
- 이분탐색을 이용해본다.
💡코드
def solution(n, times):
# left = 최소시간 , right = 최대시간
left = 1 # 최소시간은 1분이상이라고 문제에 명시
right = max(times) * n # 모든 사람이 가장 느린 심사관에게 심사를 받을 때가 최대시간
while left < right:
mid = (left + right) // 2
# total = 각 심사관이 mid 시간 동안 심사할 수 있는 사람의 수를 계산
total = sum(mid // time for time in times)
# total이 n 이상이면 가능한 시간을 "줄이기" 위해 right = mid
if total >= n:
right = mid
# total이 n 미만이면 가능한 시간을 "늘리기" 위해 left = mid + 1
else:
left = mid + 1
# 최종적으로 left가 최소시간을 가리키게 됨.
return left
💡시간복잡도
- 이분탐색이므로 O(log N)
💡 틀린 이유
- 보자마자 DP로 푸는 거라고 생각했다. if 빈 심사관이 생겼다면: time = min(빈 곳에 바로 들어가기, 기다렸다가 더 짧은 사람 들어가기) 이렇게 생각을 했는데.... 심사관이 10만명? 그럼 모든 심사관에 대해서 체크해야하는지도 의문이었고 막막했다.
💡 틀린 부분 수정 or 다른 풀이
total = sum(mid // time for time in times)
이걸 생각해내는 게 핵심이지 않았나 싶다. 결국 total값을 구하고, 이를 n과 비교해서 이분탐색을 해나가야했다.
💡 느낀점 or 기억할정보
- n이 10억 ... 너무 크다고 생각은 했는데 이럴 땐 거의 확정적으로 O(log N)을 떠올려야하는 것 같다.
- 문제를 잘 못풀었고, 이해를 못했다는 느낌을 받는다. 나중에 다시 시도해봐야한다. N이 지나치게 큰 것을 보고 이분탐색을 떠올려도 아마 풀지 못했을 것 같다...
반응형
'알고리즘 > 코테 스터디 (2024)' 카테고리의 다른 글
1654 랜선 자르기 (0) | 2024.07.31 |
---|---|
2805 나무 자르기 (0) | 2024.07.30 |
2661 좋은수열 (0) | 2024.07.27 |
1759 암호 만들기 (1) | 2024.07.26 |
1182 부분수열의 합 (0) | 2024.07.25 |