1. 관련 문제 🎯
문제 : 백준 2343 기타 레슨 🎸
난이도 : 실버 1
2. 문제 소개 🧩
1️⃣ 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.
- 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
2️⃣ M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다.
3️⃣ 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
4️⃣ 단, M개의 블루레이는 모두 같은 크기이어야 한다.
간단하게 예시를 살펴보면,
- 블루레이 1 : {1,2,3,4,5}, 블루레이 2 : {6,7}, 블루레이 3 : {8,9}로 강의를 나누어보자!
➡️ 첫 번째 조건 : "블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다." 🅾️
➡️ 두 번째 조건 : "M개의 블루레이는 모두 같은 크기이어야 한다."를 지키기 위해서, 블루레이 1의 크기 = 15, 블루레이 2의 크기 = 13, 블루레이 3의 크기 = 17이므로 블루레이의 크기를 17로 잡으면 모든 블루레이의 크기가 동일해지며 각각의 블루레이마다 강의를 담을 수 있다. 🅾️
3. 틀린 문제 풀이 🖌️
맨처음에는 문제를 풀 때, 이진 탐색은 정렬을 해야 하는데 강의 순서가 변경되면 안되므로 구간합(prefix_sum) 배열을 사용하여 문제를 풀려고 했다!!
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N = 0, M =0; //총 강의 수, 총 블루레이의 개수
cin >> N >> M;
int prefix_sum[N+1]; //구간 합
long long lecture_sum = 0;
int lecture[N];
vector<int> answer;
for(int i=0; i<N; i++){
cin>>lecture[i];
lecture_sum += lecture[i];
}
long long min_sum = lecture_sum / M; //최소 블루레이당 강의 시간
prefix_sum[0] = 0;
for(int i=0; i<N; i++){
prefix_sum[i+1] = lecture[i] + prefix_sum[i];
}
int mid = 0, start = 1, end = N;
bool check = false;
answer.push_back(0);
for(int i=0; i<M-1; i++){
while(start<=end){
mid = (start + end) / 2;
if(prefix_sum[mid] > min_sum){
end = mid - 1;
}
else if (prefix_sum[mid] == min_sum){
check = true;
break;
}
else{
start = mid + 1;
}
}
if(check == true){
answer.push_back(min_sum);
min_sum += prefix_sum[mid];
}
else{
answer.push_back(prefix_sum[end-1]-answer[i]);
min_sum += prefix_sum[end-1]-answer[i];
}
check = false;
start = end;
end = N;
}
answer.push_back(prefix_sum[N]-prefix_sum[start-1]);
sort(answer.begin(), answer.end());
cout<<answer[M]<<"\n";
}이렇게 풀었더니 틀렸다🥲
따라서 다른 사람들의 풀이를 참고하여 해결하기로 하였다.
4. 맞춘 문제 풀이 🖌️
참고 사이트 : https://chanhuiseok.github.io/posts/baek-22/
여기에서 이진탐색은 구하고자 하는 값이 블루레이의 크기이다!
블루레이의 최소 크기를 low로 잡고, 블루레이의 최대 크기를 high로 잡아본다.
이때 블루레이의 최소 크기(=low)는 블루레이의 개수가 N개일 때를 의미한다.
그리고 블루레이의 최대 크기(=high)를 블루레이의 개수가 1개일 때를 의미한다.
예시를 보면서 더 자세하게 살펴보자🔥
이때, 블루레이의 개수는 최소 1개, 최대 9개가 생길 수 있다.
1️⃣ 블루레이의 개수 = 1일 때, 블루레이의 크기 = 45 (=high)
➡️ 블루레이 : {1,2,3,4,5,6,7,8,9}
2️⃣ 블루레이의 개수 = 9일 때, 블루레이의 크기 = 9 (=low)
➡️ 블루레이 : {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}
☝️ 이때, mid = (low + high)/2 = (45+9) / 2 = 54 /2 = 27
임의로 블루레이 크기(mid)를 정하고 나서, 블루레이 개수(cnt)가 M(=3개)보다 많아지면 블루레이의 크기를 늘린다. (블루레이의 크기 ⬆️ 블루레이 개수 ⬇️)
블루레이 개수가 M(=3)보다 작으면, 블루레이의 크기를 줄인다.
5. 전체 코드 🔑
위의 풀이를 그대로 코드로 구현하면 된다!!😄
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N = 0, M =0; //총 강의 수, 총 블루레이의 개수
cin >> N >> M;
long long lecture_sum = 0; //블루레이 개수가 N일때, 블루레이의 크기
long long lecture_max = 0; //블루레이 개수가 1일때, 블루레이의 크기
long long lecture[N];
for(int i=0; i<N; i++){
cin>>lecture[i];
lecture_sum += lecture[i];
lecture_max = max(lecture_max, lecture[i]);
}
long long high = lecture_sum;
long long low = lecture_max;
long long mid = 0;
while(low <= high){
int cnt = 0; //블루레이의 개수
int sum = 0;
mid = (high + low) / 2;
for(int i=0; i<N; i++){
sum += lecture[i];
if(sum > mid){
sum = lecture[i];
cnt++;
}
}
if(sum > 0){
cnt++;
}
if(cnt > M){ //블루레이의 크기를 늘려야 한다.
low = mid + 1;
}
else{
high = mid - 1;
}
}
cout<<low<<"\n";
}이때, long long이 반복적으로 사용되므로
typedef long long ll를 위쪽에 선언하여,
long long lecture_sum = 0를ll lecture_sum = 0으로 바꿀수도 있다
6. 결과 🏆
