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

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

프로그래머스

풀이 방법

통과할 수 있는 level 중에 가장 작은 level을 선택해야 한다. 

해당 부분을 통해 이분 탐색을 이용한 완전 탐색으로 풀이해야 겠다고 생각했다.

문제에서 해결을 못하는 경우는 없다고 했으므로 가장 최댓값을 limit으로 최솟값을 1로 설정하고 이분 탐색을 진행했다.

이때 해당 level로 통과를 할 수 있다면 right = mid -1로 하여 작은 level에 대한 시도를 하며

통과를 하지 못한다면 left = mid + 1을 통해 level을 높여 주었다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;
long long prev_ans = 0;

int cal_time(int level, int diff, int time_prev, int time_cur) { 
    if (level >= diff) return time_cur; // 한 번에 푸는 경우
    else { // 여러 번 시도
        return (diff - level) * (time_prev + time_cur) + time_cur;
    }
}

bool can_solve(vector<int> diffs, vector<int> times,int level, long long limit) {
    long long spend_time = 0;
    for (int i = 0;i < diffs.size();i++) {
        if (i == 0) { // 0 인경우
            spend_time += cal_time(level, diffs[i], 0, times[i]);
        }
        else { // prev_time이 존재하는 경우
            spend_time += cal_time(level, diffs[i], times[i-1], times[i]);
        }
    }    
    if (spend_time > limit) return false;
    else {
        prev_ans = level;
        return true;
    }
}
int solution(vector<int> diffs, vector<int> times, long long limit) {
    // 이진 탐색 하면 된다.
    int answer = 0;
    long long left = 1;
    long long right = limit;       
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (can_solve(diffs, times, mid, limit)) { // 가능 한 경우
            right = mid - 1;            
        }
        else { // 불가능 한 경우
            left = mid + 1;
        }
    }
    answer = prev_ans;
    return answer;
}