[Programmers] Lv.2 _ [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

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