문제

https://school.programmers.co.kr/learn/courses/30/lessons/340212

---

입력

• 퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs
• 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times
• 전체 제한 시간 limit

---

출력

• 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값

---

풀이

제한조건

• 1 ≤ diffs의 길이 = times의 길이 = n ≤ 300,000
• diffs[i]는 i번째 퍼즐의 난이도, times[i]는 i번째 퍼즐의 소요 시간입니다.
• diffs[0] = 1
• 1 ≤ diffs[i] ≤ 100,000
• 1 ≤ times[i] ≤ 10,000
• 1 ≤ limit ≤ 1015
• 제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 입력으로 주어집니다.

접근방법

이분 탐색, 매개변수탐색

제한조건을 먼저 살펴보자.
limit의 범위가 10^15으로 매우 크다.
모든 경우의 수를 따져가며 최소시간을 찾기에는 시간 초과가 발생할 것이다.

경우의 수를 반으로 줄여가며 탐색할 수 있는 이분 탐색을 활용해보자.

우선 문제를 해결하기 위해 사용되는 시간을 x라고 해 보자.
현재의 숙련도를 n이라고 가정하고, 문제의 수식에 따라 소요되는 시간 x를 구할 수 있을 것이다.
이때 숙련도 n이 클수록 소요되는 시간 x가 작아지고,
숙련도 n이 작을수록 소요되는 시간 x는 커질것이다 라고 우리는 추측할 수 있다.

- 문제를 해결하기 위한 최소시간 1
- 문제를 해결하기 위한 최대시간 limit
   (제한 시간 내에 퍼즐을 모두 해결할 수 있는 경우만 주어지기때문)

이제 둘 사이에서 중간값을 조율해나가며 적당한 시간을 찾으면 된다.
이때 문제에서 주어진 계산식에 따라 계산을 했을 때 나오는 값 x가
limit보다 크면서, 가장 limit에 가까운 수를 찾으면 된다.

그 때의 숙련도보다 1만큼 더 높은 숙련도를 가진다면 반드시 limit보다 빠른시간에 해결이 될 것이기 때문.

따라서 이분탐색을 통해 구한 min 값 + 1이 구하고자 하는 숙련도의 최솟값임을 알 수 있다.

---

코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        long min = 1;
        long max = limit;
        int len = diffs.length;
        while (min <= max) {
            long level = (min + max) / 2;
            long spentTime = 0;

            for (int i = 0; i < len; ++i) {
                if (level < diffs[i])
                    spentTime += (times[i] + times[i - 1]) * (diffs[i] - level) + times[i];
                else
                    spentTime += times[i];
            }

            if(spentTime > limit)
                min = level + 1;
            else
                max = level - 1;
        }
        return (int)min;
    }
}