https://school.programmers.co.kr/learn/courses/30/lessons/340212
풀이
퍼즐 난이도: diffs
소요 시간: times
제한 시간: limit
숙련도: level
퍼즐 난이도가 숙련도보다 낮거나 같으면 (diffs[i] <= level)
해당 퍼즐의 소요 시간 (times[i]) 만큼만 소요.
퍼즐 난이도가 숙련도보다 높으면 (diffs[i] > level)
해당 퍼즐의 이전 소요 시간 + 현재 소요 시간 을 난이도 - 숙련도 만큼 수행 후 현재 소요 시간 추가 소요.
퍼즐의 모든 소요 시간의 합이 limit보다 작은 숙련도 최솟값 구하기.
퍼즐의 숙련도는 최소: 1, 최대: max(diffs) 로 범위가 정해져있으며,
수행 가능한 숙련도의 경계값을 찾는 문제이기 때문에 이분탐색 문제임을 알 수 있다.
코드
def bsearch(diffs, times, limit, level):
n = len(diffs)
total = 0
for i in range(n):
if diffs[i] > level:
curPrev = times[i]
if i > 0:
total += (curPrev + times[i - 1]) * (diffs[i] - level) + curPrev
else:
total += curPrev * (diffs[i] - level) + curPrev
else:
total += times[i]
if total <= limit:
return True
else:
return False
def solution(diffs, times, limit):
low = 1
high = max(diffs)
while low <= high:
mid = (low + high) // 2
result = bsearch(diffs, times, limit, mid)
if result:
high = mid - 1
else:
low = mid + 1
return low
'Algorithm > Programmers' 카테고리의 다른 글
[Programmers] Lv.2 _ [PCCP 기출문제] 2번 / 석유 시추 (0) | 2025.01.18 |
---|---|
[Programmers] Lv.2 _ [PCCP 기출문제] 3번 / 충돌 위험 찾기 (0) | 2025.01.06 |
[Programmers] Lv.1 _ 가장 많이 받은 선물 (1) | 2024.06.11 |