BOJ 2343번: 기타 레슨

문제

문제 바로가기> BOJ 2343번: 기타 레슨

2343번: 기타 레슨

 

풀이

매개 변수 탐색을 이용해서 가능한 블루레이의 크기 중 최소를 구하는 문제다.

주의할 점은 상한(high)을 설정하는 부분이다.

처음에 high를 10,001으로 설정했는데 바로 틀렸다,,

생각해보니, 각 강의의 길이가 10,000분을 넘지 않는 것이지,

블루레이의의 크기는 당연히 10,000분을 넘을 수 있기 때문!! 이 부분을 주의해 줘야 할 것 같다!

 

각 강의당 길이가 10,000분이므로, 10000*100000 = 10억이고,

따라서 이분탐색을 하지 않고 brute-force 방식으로 문제를 해결하면 시간초과가 발생한다!

 

#include<iostream>
#define MAX 100001
#define INF 1000000001 // 10000 * 100000
using namespace std;

int video[MAX];
int N, M, ans = 0; 
int low = 0, high = INF;

void input() {
	cin >> N >> M;
	for(int i = 0; i < N; i++) cin >> video[i];
}

bool check(int size) { //  블루레이 제한 크기
    int s = 0, cnt = 0; // 현재 크기, 블루레이 개수
    for(int i=0; i<N; i++){
        if(size < video[i]) return false; // 담을 수 없음
        if(size < s+video[i]){
            cnt++;
            s = video[i];
        }
        else s+=video[i];
    }
    if (s > 0) cnt += 1;
    if (cnt <= M) return true;
    return false;
}

void solution() { // 가능한 블루레이 크기중 최소를 출력 (매개변수 탐색)
	while (low <= high) {
		int mid = (low + high) / 2;
		if (check(mid)) high = mid - 1; // 블루레이의 크기를 더 낮춰도 됨
		else low = mid + 1; // 블루레이의 크기를 더 늘려야 함
	} cout << low;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	solution();
}