알고리즘/백준
[백준 2343] 기타 레슨 (C++)
라이언납시오
2020. 3. 9. 23:05
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 레슨의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 레슨과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가
www.acmicpc.net
1. 주의할 점
- 이분탐색의 조건을 잘 따져줘야한다(low<=high, low=mid+1, high = mid-1) -> 이 부분때문에 많이 틀렸는데 아직도 많이 헷갈리는 부분이다.
2. 구현
- 이분탐색에서 High의 경우 모든 레슨 길이의 합을, Low에는 0을 넣고 시작한다
#include <iostream>
#include <algorithm>
using namespace std;
long long result = -1;
int arr[100000];
int num, blue;
bool binarySearch(int val) {
int cnt = 1;
long long tot = 0;
for (int i = 0; i < num; i++) {
if (arr[i] > val)
return false;
tot += arr[i];
if (tot > val) {
tot = arr[i];
cnt++;
}
}
if (cnt <= blue) return true;
else return false;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
long long sum = 0;
cin >> num >> blue;
for (int i = 0; i < num; i++) {
cin >> arr[i];
sum += arr[i];
}
long long low = 0, mid, high = sum;
while (low <= high) {
mid = low + (high - low) / 2;
bool flag = binarySearch(mid);
if (flag) {
high = mid - 1;
result = mid;
}
else low = mid + 1;
}
cout << result;
system("pause");
return 0;
}728x90
반응형