백준 2343 기타레슨 풀이(c++)
in Algorithm on 알고리즘
이분탐색을 배웠다. 백준 2343, 2792, 6236 문제 풀이
1. 2792
#include <bits/stdc++.h>
using namespace std;
int n, m, a[300004];
int result = 987654321;
bool check(int val) {
int ret = 0;
for (int i = 0; i < m; i++) {
ret += a[i] / val;
if (a[i] % val) ret++;
}
return ret <= n;
}
int main() {
cin >> n >> m;
int l = 1; int r = 0;
for (int i = 0; i < m; i++) {
cin >> a[i];
r = max(r, a[i]);
}
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) {
result = min(result, mid);
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << result;
}
이분탐색으로 문제를 풀어서 결정문제로 만들어서 풀면 되는 문제. 보석을 학생들에게 나누어 주는 문제.
각 사람이 받을 수 있는 보석의 개수를 이분탐색으로 찾으면 되는 문제였다.
2. 2343
#include <bits/stdc++.h>
using namespace std;
int n, m, ret, a[100004], sum, mx;
bool check(int val) {
if (mx > val) return 0;
int temp = val; //val이 계속 바뀌어서 임시 보관
int cnt = 0; //그룹의 개수
for (int i = 0; i < n; i++) {
if (val - a[i] < 0) { //더이상 현제 그룹에 새 강의를 넣지 못한다.
val = temp; //새로운 그룹 시작
cnt++; //그룹 추가
}
val -= a[i]; //해당 강의 숫자를 차감
}
if (val != temp) cnt++;
return cnt <= m;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++ ) {
cin >> a[i];
sum += a[i]; //이분 탐색의 hi는 모든 강의를 더한 값
mx = max(mx, a[i]); //한 강의가 mx보다 작지 못한다.
}
int lo = 0; int hi = sum;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(mid)) { //mid 값으로 나누기가 가능
hi = mid - 1; //그럼 혹시 더 작은 값으로 나눌 수 있을까?
ret = mid; //mid값 ret에 저장
}
else { //너무 크기가 작아서 불가능 하다.
lo = mid + 1; //블루레이 크기를 증가하는 방향으로
}
}
cout << ret;
}
2343문제를 풀기 전에 비슷한 문제일 2792 보석상자 문제를 풀었다. 보석상자 문제는 한 사람에게 몇개를 나누어 줄지를 이분탐색으로 찾는 것이었다.
그 이후에 2343문제를 풀어서 그러가 이분탐색으로 풀 수는 있겠는데 자꾸 알고리즘을 짜보려면 생각이 계속 막혔다.. 뭔가 잘 못 생각한 것 같았다.
알고보니 내가 보석상자처럼 한 블루레이에 몇 개의 강의를 넣을 지를 기준으로 이분탐색을 해서 안되는 거였다.. ㅜ 기타레슨 문제는 각 강의 블루레이의 크기를 최소화 하는 문제이다.
그래서 이분탐색의 대상을 블루레이 하나의 크기으로 해야했다! 보석상자는 각 사람에게 최소한의 보석을 분배할 수 있도록하는 것이 었기 때문에 각 사람이 받을 수 있는 보석의 개수를 대상으로 해야했던 것이다.
계속 보석상자 문제처럼 풀려고 해서 안됬던 것..ㅜ
이분탐색인 것을 눈치 채도 어떤 것을 기준으로 이분탐색을 할지도 명확히 해야한다.
이분 탐색은 학교 수업시간에서 탐색법을 배우면서 배웠던 방법이었다. 그 시간 복잡도를 배우면서 같이 배웠던 것 같은데.. 그때 당시 그냥 숫자를 찾을 때 시간 복잡도가 logN 이라서 시간이 짧게 걸린다. 정도만 기억하고 넘어갔던 것 같다.
그래서 그냥 단순히 탐색 문제에만 쓰인다고 생각했다. 하지만 백준 문제를 풀면서 이분 탐색이 이렇게도 응용될 수 있는지 처음 알게 되어서 너무 신기했다. 
3. 6236
#include <bits/stdc++.h>
using namespace std;
int n, m, a[100004], mx, ret, sum;
bool check(int mid) {
if (mx > mid) return 0;
int cnt = 0; int temp = mid;
for (int i = 0; i < n; i++) {
if (mid - a[i] < 0) {
mid = temp; //새 그룹생성
cnt++; //그룹 추가
}
mid -= a[i];
}
if (mid != temp) { //마지막 그룹
cnt++;
}
return cnt <= m;
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> a[i];
sum += a[i];
mx = max(mx, a[i]);
}
int l = 1; int r = sum;
int mid = 0;
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
ret = mid;
}
else {
l = mid + 1;
}
}
cout << ret;
}
2343 문제와 비슷하게 풀면 되는 문제. 말이 좀 복잡해서 그렇지 2343 문제와 거의 똑같은 문제이다. 앞에서 몇번 틀려서 그런지 이번 문제를 수월하게 풀 수 있었다.
여기서 좀 헷갈렸던게 m번을 맞추기 위해서 k가 더 크더라도 일부러 맞출 수 있다는 점이었다. 이걸 어떻게 찾지 고민을 했었는 데 그룹 수를 의미하는 cnt의 값이 m보다 작으면 더 쪼개서 맞출 수 있기 때문에 return cnt <= m으로 하면 되었다.
