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

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

프로그래머스

 

문제의 조건을 보면, 배열의 크기(diffs, times)가 300,000이다.

300,000 자체는 순회할 만 하지만, 매 순회마다 검사하는 시간제한(limit)이 10의 15승이다.

따라서, 이는 숙련도를 1씩 올리거나 내리면서 찾으려고 하면 시간 초과가 날 것임을 알 수 있다.

 

숙련도는 아무리 높아도 퍼즐(diffs)의 최대 난이도보다 높을 수 없다.

(퍼즐의 첫 값이 1로 고정이기 때문)

 

따라서, 처음 검사하는 숙련도를 퍼즐의 최대 난이도 / 2로 지정하고 문제 풀이를 시작한다.

여기서 구한 퍼즐의 최대 난이도를 Max라 저장하고, 이를 최대 숙련도로 계속 업데이트한다.

 

문제 풀이에 걸리는 시간이 시간제한을 넘어서는 경우, 현재 숙련도를 올려야 한다.

(answer += (Max - answer) / 2)

 

시간제한을 넘어서지 않는 경우, 현재 숙련도를 낮춰도 된다.

(Max = answer, answer /= 2)

 

이를 계속 반복하다 보면, 이전 숙련도와 새로 얻은 숙련도가 같아지는 시점이 오게 된다.

(숙련도를 낮추면 시간이 부족하고, 숙련도를 올리면 시간이 남는 숙련도)

 

이 때는 (Max - answer) / 2를 해도 값이 변하지 않는 상태인데 이때부턴 거의 정답에 가까운 상태이니 숙련도를 1씩 올리며 검사한다.

숙련도가 최대 숙련도와 같거나 높으면 그 값이 최적의 숙련도이다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool IsLevelUp(const vector<int>& diffs, const vector<int>& times, const long long& limit, const int& answer)
{
	long long Sum = times[0];
	for (int i = 1; i < diffs.size(); ++i)
	{
		if (Sum > limit) return true; // 문제 풀이 시간이 시간 제한을 넘은 경우, 숙련도를 올려야 함
		if (diffs[i] <= answer) Sum += times[i];
		else Sum += ((times[i] + times[i - 1]) * (diffs[i] - answer)) + times[i];
	}
	if (Sum > limit) return true; // 문제 풀이 시간이 시간 제한을 넘은 경우, 숙련도를 올려야 함
	return false; // 시간 제한이 남았으니, 숙련도를 내려도 됨
}

int solution(vector<int> diffs, vector<int> times, long long limit) {
	// 가장 큰 문제 난이도/2를 시작 레벨로 잡음
	int Max = *max_element(diffs.begin(), diffs.end()), answer = Max / 2;

	while (true)
	{
		int Save = answer; // 현재 숙련도를 저장
		bool Flag = IsLevelUp(diffs, times, limit, answer);

		if (Flag) answer += (Max - answer) / 2;
		else Max = answer, answer /= 2;

		if (Save == answer) answer++;
		if (answer >= Max) return answer;
	}

	return answer;
}