일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 백준#BOJ#1939#중량제한
- 백준#boj#16932#모양만들기
- 백준#BOJ#8012#한동이는영업사원
- 백준#BOJ#2615#오목
- 백준#BOJ#14501#퇴사#브루트포스
- 백준#BOJ#12865#평범한배낭
- 백준#boj#12755
- Today
- Total
순간을 성실히, 화려함보단 꾸준함을
[ boj : 2343 ] 기타 레슨 본문
https://www.acmicpc.net/problem/2343
해설 : 이분탐색 문제 특징이 문제를 읽었을때 어떤 범위를 줄여나가며 답을 갱신해야되는 특징을 가지고 있는 것 같습니다.
이번 문제도 보시면 블루레이의 크기를 최소로 하려면 결국 x크기에 대해서 너무 오버한다면 줄여나가고 반대로 너무 빡빡하면 키우고 이런식으로 답에 해당하는 값을 찾기 위해 범위를 줄여나가는 것이죠.
정렬이 된 상태에서 원하는 수를 찾기 위한 방법을 생각해보시면 이 문제도 결국 근본적인 특징은 다를게 하나도 없는 것이죠.
그러면 문제로 다시 돌아가서 N개의 강의가 존재하고 M개의 블루레이를 만들려고 합니다.
이때 반드시 연속된 강의를 한묶음으로 만들고 그 묶음에 속해있는 강의 크기의 총 합에 대해 최소값을 구해야 합니다.
그럼 제일 처음 생각해볼만 한건 그냥 모든 경우의 수를 전부 해보면 되겠죠???ㅋㅋㅋ
근데 N의 범위를 보면 절대 그건 할 수 없다는 걸 알 수 있습니다. 다른 방법을 찾다보니 "답을 찾아나아가는 것이 아니라 그냥 답을 미리 가정하면" 안될까요?
즉, 현재 답이 x 라고 한다면 이 x에 대해서 답이 유효하다면? 답이 될 수 있는 후보에 저장을 해두는 것입니다.
9 3
1 2 3 4 5 6 7 8 9
문제에서 연속된 강의들이니 답으로 가정한 x에서 하나씩 원소들을 빼보는 것입니다. 그러다가 0보다 작아지게 되면?블루레이가 하나 더 필요하다라는 뜻이므로 count 해주면 되겠죠.
이렇게 범위를 좁혀나가서 답을 도출해 내면 됩니다.
주의할 점은 left를 0으로 시작하는 것이 아니라 주어진 강의들 중 가장 높은 값으로 선택해야 합니다. 아무리 최소라도 블루레이의 크기는 가장 큰 강의보다 작아지면 안되기 때문입니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int SIZE = (int)1e5 + 1;
int n, m;
ll arr[SIZE];
void solve();
int f(ll x);
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--)solve();
return 0;
}
void solve()
{
cin >> n >> m;
ll l = 0, r = (ll)1e9 + 1;
for (int i = 0; i < n; i++) {
cin >> arr[i];
l = (l < arr[i] ? arr[i] : l);
}
ll ans;
while (l <= r) {
ll mid = (l + r) / 2;
if (f(mid) > m)l = mid + 1;
else {
ans = mid;
r = mid - 1;
}
}
cout << ans;
}
int f(ll x)
{
int cnt = 1;
ll p = x;
for (int i = 0; i < n; i++) {
if (p - arr[i] < 0) {
cnt++;
p = x;
}
p -= arr[i];
}
return cnt;
}
'알고리즘,SQL > 백준,BOJ' 카테고리의 다른 글
[ boj : 16507 ] 어두운 건 무서워 (0) | 2022.01.29 |
---|---|
[ boj : 21608 ] 상어 초등학교 (0) | 2022.01.28 |
[ boj : 22868 ] 산책(small) (0) | 2022.01.26 |
[ boj : 22942 ] 데이터 체커 (0) | 2022.01.22 |
[ boj : 7573 ] 고기잡이 (0) | 2022.01.22 |