퍼즐 게임 챌린지

문제 정의

• 주어진 diffs 리스트는 각 구간별로 발생하는 차이를 나타내며, times 리스트는 각 구간의 작업 시간입니다.
• 특정 구간에서 diffs[i]가 임계값보다 큰 경우, 해당 구간을 줄이기 위해 추가 작업이 필요합니다.
• limit은 총 작업 시간의 제한을 나타내며, 이 시간을 초과하지 않는 선에서 diffs의 최대값을 가능한 한 낮춰야 합니다.

코드 구현

def solution(diffs, times, limit):
    answer = 0
    left = 1
    right = max(diffs)
    while left <= right:
        cnt = 0
        mid = (left + right) // 2
        for i in range(len(diffs)):
            if diffs[i] > mid:
                cnt += (times[i] + (times[i-1] if i != 0 else 0)) * (diffs[i] - mid)
            cnt += times[i]
            if cnt > limit:
                break
        if cnt > limit:
            left = mid + 1
        else:
            answer = mid
            right = mid - 1
    return answer

코드 설명

1. 이진 탐색의 초기값 설정
   diffs에서 최댓값을 right로, 1을 left로 설정하여 구간을 잡습니다. mid는 이 구간의 중간값으로 설정되며, 최적화 목표가 되는 기준 값입니다.
2. 총 작업 시간 계산
   각 구간의 diffs[i]가 mid보다 클 경우, 줄이기 위해 추가 작업이 필요합니다. 이때 (diffs[i] - mid)에 따라 추가적인 작업 시간이 더해지며, cnt 변수에 누적됩니다. 만약 cnt가 limit을 초과하면 해당 mid 값이 조건에 부합하지 않음을 의미합니다.
3. 이진 탐색 반복문
   조건에 따라 left 또는 right 값을 조정해가며 탐색을 반복합니다. cnt가 limit 이하인 경우 answer 값을 업데이트하면서 더 작은 mid 값으로 탐색해 나갑니다.