M개의 블루레이를 꼭 사용하고, 모두 같은 크기이되 최소 크기의 블루레이를 사용한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
// 한 블루레이 크기를 size라고 할 때, 모든 강의를 다 담는 것이 가능한 지 반환
bool check (const vector<int> courses, int size) {
int cnt = 0;
int ret = 0; // 필요한 블루레이 개수
for (int i = 0; i < n; i++) {
cnt += courses[i];
if (i < n - 1 && cnt + courses[i + 1] > size) {
cnt = 0;
ret++;
if (ret > m) return false;
}
}
if (cnt != 0) ret++;
if (ret <= m) return true;
return false;
}
int main() {
cin >> n >> m;
vector<int> course(n);
int sum = 0;
for (int i = 0; i < n; i++) {
cin >> course[i];
sum += course[i];
}
sort(course.begin(), course.end());
int left = sum / m;
int right = sum - (m - 1);
int ret = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (check(course, mid)) {
ret = mid;
right = mid - 1;
}
else
left = mid + 1;
}
cout << ret << endl;
return 0;
}
강의의 순서를 바꾸면 안된다는 조건을 무시하고 구현해서 “틀렸습니다”가 떴다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
// 한 블루레이 크기를 size라고 할 때, m개의 블루레이에 모든 강의를 다 담는 것이 가능한 지 반환
bool check (const vector<int> courses, int size) {
long long cnt = 0;
long long ret = 0; // 필요한 블루레이 개수
for (int i = 0; i < n; i++) {
cnt += courses[i];
if (i < n - 1 && cnt + courses[i + 1] > size) {
cnt = 0;
ret++;
if (ret == m && i != n - 1) return false;
}
}
if (cnt != 0) ret++;
if (ret <= m) return true;
return false;
}
int main() {
cin >> n >> m;
vector<int > course(n);
long long sum = 0;
for (int i = 0; i < n; i++) {
cin >> course[i];
sum += course[i];
}
long long left = 1;
long long right = sum;
long long ret = 0;
while (left <= right) {
long long mid = (left + right) / 2;
if (check(course, mid)) {
ret = mid;
right = mid - 1;
}
else
left = mid + 1;
}
cout << ret << endl;
return 0;
}
아무리 고쳐도 .. “틀렸습니다”가 뜬다.
해설
이 문제는 주어진 숫자들을 M개의 그룹으로 나누는 문제이다. 블루레이 크기는 그룹에 속해있는 레슨의 합, 즉 그룹의 합이다. 블루레이의 크기, 즉 그룹의 크기의 최댓값을 최소로 만들어야하는 문제이므로 이분 탐색을 사용한다.
N개의 강의를 M개의 블루레이에 담을 수 있고, 그때의 크기가 10이라면 10보다 큰 블루레이의 크기로도 M개에 담을 수 있다.
left의 초기값 : 강의 크기의 최댓값 (적어도 하나의 강의를 녹화할 수 있어야 하기 때문에)
right의 초기값 : 강의 크기의 전체 합 (모든 강의를 하나의 블루레이에 저장하는 경우)
#include <iostream>
#include <vector>
using namespace std;
int n, m;
// 한 블루레이 크기를 size라고 할 때, m개의 블루레이에 모든 강의를 다 담는 것이 가능한 지 반환
bool check (const vector<int> courses, int size) {
int sum = 0; // 블루레이에 담는 강의의 합
int cnt = 1; // 블루레이 개수
for (int i = 0; i < n; i++) {
if (sum + courses[i] > size) {
cnt++;
sum = courses[i];
}
else
sum += courses[i];
}
return cnt <= m;
}
int main() {
cin >> n >> m;
vector<int > course(n);
int left = 0, right = 0;
for (int i = 0; i < n; i++) {
cin >> course[i];
if (course[i] > left) left = course[i];
right += course[i];
}
int ret = 0;
while (left <= right) {
long long mid = (left + right) / 2;
if (check(course, mid)) {
ret = mid;
right = mid - 1;
}
else
left = mid + 1;
}
cout << ret << endl;
return 0;
}
나는 여기서 left의 초기값을 설정하지 못해 에러를 마주쳤다. left의 초기값은 적어도 하나의 조건만 만족하는 경우를 찾아 설정한다. 여기에서는 모든 강의 중 적어도 하나는 블루레이에 실어야 하므로, 가장 큰 레슨의 크기를 초기값으로 설정하면 각각의 레슨을 블루레이에 녹화하는 것이 가능하기 때문에 위와 같이 설정하였다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
// 구간 점수의 최댓값이 k가 되도록 m개의 구간을 만드는 것이 가능한 지 검사
bool calc(vector<int> num, int k) {
int ret = 1; // 구간 수
int index = 0;
while (index < (int)num.size()) {
int last_min = num[index];
int last_max = num[index];
while (index < (int) num.size()) {
index++;
if (last_min > num[index]) last_min = num[index];
if (last_max < num[index]) last_max = num[index];
if (last_max - last_min > k) {
// 현재 index부터 다음 구간으로 포함한다.
ret++;
break;
}
**// 남은 구간 처리
int remain = m - ret;
if (n - index - 1 == remain) {
ret++;
break;
}**
}
**index++;**
}
return ret <= m;
}
int main() {
cin >> n >> m;
vector<int> numbers(n);
for (int i = 0; i < n; i++)
cin >> numbers[i];
int left = 0;
int right = 9999;
int ret = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (calc(numbers, mid)) {
ret = mid;
right = mid - 1;
}
else
left = mid + 1;
}
cout << ret << endl;
return 0;
}
초기 코드이다.