[프로그래머스 Lv.2] 퍼즐 게임 챌린지

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

프로그래머스

 

문제를 보고 조건을 설정해보자.

 

조건 세우는 건 어렵지 않았다.

 

이제 남은 건 시간 복잡도 안에 해결을 해야하는데, limits가 10^15였다.

 

바로 int 범위를 벗어나는... O(n) 해결 시 바로 시간 초과가 뜰 게 분명했다.

 

그래서 이분 탐색을 생각했다.

 

O(log(limits)) * n 을 해도 시간초과가 뜨지 않는다!

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    long long cnt = 0;
    
    long long lo, hi, mid;
    
    lo = 0;
    hi = limit;
    
    // 이분탐색
    while(lo + 1 < hi) {
        mid = (lo + hi) / 2;
        // diff, level 비교
        for(int i = 0; i < diffs.size(); i++) {
            if (diffs[i] <= mid) {
                cnt += times[i];
            }
            else {
                // 틀린 횟수
                int temp = (diffs[i] - mid);
                int wrong = temp * (times[i-1] + times[i]) + times[i];
                cnt += wrong;
            }
        }
        
        if (limit >= cnt) {
            hi = mid;
        } else {
            lo = mid;
        }
        cnt = 0;
    }
    
    answer = hi;
    return answer;
}