[Medium] Minimum Time Required
백준 기준 실버1~골드5 문제정도 될 것 같다.
한줄 요약 : 이분 탐색 문제.
문제
문제는 다음과 같다. 우선 이 문제는 Search 카테고리의 문제이다.
물건을 만드는 기계들이 있다. 이 기계들은 동시에 작동하며 각 기계는 물건 하나를 생산하는데 몇 일이 걸린다. 예를 들어 machines = [2,3,2] 로 주어진다면, 3개의 기계가 각각 물건 하나를 생산하는데 걸리는 시간이 2일, 3일, 2일 이다. 물건을 10개 만드는 것이 목표라면, 아래와 같은 스케줄을 가지면서 최소 8일 후에 10개를 생산할 수 있다.
물건하나를 생산하는데 몇일이 걸리는지 나열된 배열과 목표 물건의 개수가 주어졌을때, 최소 몇일이 걸리는지 맞추는 문제이다.
솔루션
우선 그냥 무지성으로 완전탐색(전수조사)를 실시해보았다. 몇몇 테케는 통과하지만 이외에는 당연히 시간초과가 난다.
완탐이 안되기때문에 다음으로 시도해본 방법은 이분탐색(Binary Search)으로 이분탐색을 수행하기 위해선 두 가지가 먼저 준비되어한다.
1. 오름차순된 배열
2. 답이 존재할 수 있는 정의역
우선 주어진 기계의 능력이 담긴 배열을 오름차순 정렬한다. 그리고 목표(걸리는 일수, mid)를 찾기위해 정의역을 설정해야하는데 가장 빨리만든다면 0일이 걸릴 것이고, 가장 비효율적으로 만든다고하면 제일 능력이 안좋은 기계로만 만들었을 때이다. 따라서 정의역은 0 ~ max(machine)*Goal 이 될 것이다.
이제 mid를 찾아야하는데 mid 는 Goal 만큼의 아이템을 만드는데 '몇 일 걸리는지(mid)' 이므로 mid 를 machine[n] 으로 나누면 해당 일 수가 주어졌을때 기계가 몇 개를 생산하는 지 알 수있다. 일종의 파라메트릭 서치(Parametric Search) . 나는 해당일수(mid)동안 생산한 아이템의 양을 변수 ex에 저장했다.
이제 이 ex라는 변수를 이용하여 이것이 Goal 보다 큰 지, 작은 지를 비교하여 이분 탐색을 수행하면 된다.
코드는 다음과 같다.
#include <bits/stdc++.h>
using namespace std;
vector<string> split_string(string);
// Complete the minTime function below.
long minTime(vector<long> machines, long goal) {
sort(machines.begin(), machines.end());
long l = 0, r = machines[machines.size()-1]*goal,res=0;
while (l < r) {
long mid = (l + r) / 2;
long ex = 0;
for (int i = 0; i < machines.size(); i++) {
ex += (mid / machines[i]);
}
if (ex >= goal) {
r = mid;
res = mid;
}
else if (ex < goal)
l = mid + 1;
}
return res;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string nGoal_temp;
getline(cin, nGoal_temp);
vector<string> nGoal = split_string(nGoal_temp);
int n = stoi(nGoal[0]);
long goal = stol(nGoal[1]);
string machines_temp_temp;
getline(cin, machines_temp_temp);
vector<string> machines_temp = split_string(machines_temp_temp);
vector<long> machines(n);
for (int i = 0; i < n; i++) {
long machines_item = stol(machines_temp[i]);
machines[i] = machines_item;
}
long ans = minTime(machines, goal);
fout << ans << "\n";
fout.close();
return 0;
}
vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});
input_string.erase(new_end, input_string.end());
while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}
vector<string> splits;
char delimiter = ' ';
size_t i = 0;
size_t pos = input_string.find(delimiter);
while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));
i = pos + 1;
pos = input_string.find(delimiter, i);
}
splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
return splits;
}
끝
댓글