[Python | 프로그래머스 | Lv_2] 퍼즐 게임 챌린지 (PCCP 기출문제)

😉 아이디어

1. _!1 ~ diffs!_ 사이 이분탐색 활용 최솟값 탐색

2. 탐색 중 _!mid(level)!_ 값 로직 의거 총 소요시간 산출 및 비교

😉 풀이

# 이분탐색
def solution(diffs, times, limit):
    low, high = 1, max(diffs)
    min_solved_time = pow(10, 15)
    
    while low <= high:
        level = (low + high) // 2
        calculated_time = calculate_solve_time(level, diffs, times)

        if calculated_time > limit: # 풀이시간 > limit => 숙련도 up
            low = level + 1
        else:
            high = level - 1
            min_solved_time = min(min_solved_time, level)
        
    return min_solved_time

def calculate_solve_time(level, diffs, times):
    total = 0
    
    for i in range(len(diffs)):
        diff = diffs[i]
        time_cur = times[i]
        
        if diff <= level:
            total += time_cur
        else:
            time_prev = times[i - 1]
            total += (time_prev + time_cur) * (diff - level) + time_cur
            
    return total

✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/340212#