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

https://school.programmers.co.kr/learn/courses/30/lessons/340212
핵심 : 이분탐색을 활용하여 검색 시간을 단축하자

public class Solution
{
    private const int MIN_LEVEL = 1;
    private int _level = MIN_LEVEL;

    public int solution(int[] diffs, int[] times, long limit)
    {
        var end = diffs[0];
        foreach (var diff in diffs)
        {
            end = end <= diff ? diff : end;
        }

        var start = 1;
        var mid = (start + end) / 2;

        var findLevel = 100000;
        while (start <= end) 
        {
            _level = mid; 
            var totalTime = GetTotalTime(diffs, times);
            if (totalTime <= limit)
            {
                findLevel = _level <= findLevel ? _level : findLevel;
                end = mid - 1;
                mid = (start + end) / 2;
            }
            else
            {
                start = mid + 1;
                mid = (start + end) / 2;
            }
        }

        return findLevel;
    }

    private long GetTotalTime(int[] diffs, int[] times)
    {
        long totalTime = 0;
        for (int i = 0; i < diffs.Length; i++)
        {
            var diff = diffs[i];
            var curTime = times[i];
            var prevTime = i - 1 >= 0 ? times[i - 1] : 0;
            if(diff > _level)
            {
                totalTime += (curTime + prevTime) * (diff - _level) + curTime;
            }
            else
            {
                totalTime += curTime;
            }
        }

        return totalTime;
    }
}