[프로그래머스 Level 2] 퍼즐 게임 챌린지 (C++)

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

프로그래머스

 

 

생각 흐름 : 최솟값을 구하는 문제 + 배열로 담을 수 없는 숫자 크기 -> 이분 탐색이라고 판단

 

 

#include <vector>

using namespace std;

bool valid(int mid, vector<int> diffs, vector<int> times, long long limit){
    
    long long sum = 0;
    
    long long different = diffs[0]-mid;
    
    if(different>0){
        sum += different*times[0]+times[0];
    }else{
        sum += times[0];
    }
    
    for(int i = 1; i<diffs.size(); i++){
        different = diffs[i]-mid;
        if(different>0){
            sum += different*(times[i]+times[i-1])+times[i];
        }else{
            sum += times[i];
        }
        if(sum>limit){
            return false;
        }
    }
    
    if(limit>=sum){
        return true;
    }
    return false;
}

int solution(vector<int> diffs, vector<int> times, long long limit) {
    int answer = 0;
    
    int start = 1;
    int end = 2147483640;
    
    while(start<=end){
        int mid = (end+start)/2;
        if(valid(mid, diffs, times, limit)){
            answer = mid;
            end = mid-1;
        }else {
            start = mid+1;
        }
    }
    
    return answer;
}