[Programmers] 퍼즐 게임 챌린지

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스

 

이분 탐색을 통해 풀 수 있는 문제였습니다.

 

	#include <vector>
	#include <algorithm>
	using namespace std;
	long long func(const vector<int>& diffs, const vector<int>& times, int level)
	{
	int n = diffs.size();
	long long totalTime = 0;
	for (int i = 0; i < n; i++)
	{
	if (diffs[i] <= level)
	{
	totalTime += times[i];
	}
	else
	{
	int mistakes = diffs[i] - level;
	// 이전 퍼즐이 없으므로, 이전 퍼즐을 다시 풀 필요가 없음
	if (i == 0)
	{
	totalTime += times[i] * (mistakes + 1);
	}
	else
	{
	int timePrev = times[i - 1];
	totalTime += (times[i] * 1LL + timePrev) * mistakes + times[i];
	}
	}
	}
	return totalTime;
	}
	int solution(vector<int> diffs, vector<int> times, long long limit)
	{
	int n = diffs.size();
	int left = 1;
	int right = 100001; // diffs[i]의 최대값이 1e5이므로 최대 숙련도를 1e5 + 1로 설정
	while (left < right)
	{
	int mid = (left + right) / 2;
	long long totalTime = func(diffs, times, mid);
	if (totalTime <= limit)
	{
	right = mid;
	}
	else
	{
	left = mid + 1;
	}
	}
	return left;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~