[인프런 C++] 43. 뮤직비디오(이진탐색 응용)

🍧 문제

DVD에는 총 N개의 곡이 들어간다. DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다.

M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이때 DVD의 크기를 최소로 하려한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

 

 

✨ 1트 (성공)

오랜만에 성공.. /(ㄒoㄒ)/~~

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
	freopen("input.txt", "rt", stdin);
	
	int n, m, cnt = 0, total = 0;
	cin >> n >> m;
	vector<int> a(n);
	
	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}
	
	int left = 0;
	int right = n-1;
	int mid;
	
	mid = (left + right) / 2;
	cnt++;
	
	while(cnt <= m){
		mid = (left + right) / 2;
		
		if(cnt == m){
			for(int i = mid; i < n; ++i){
				total += a[i];
			}
			
			break;
		}
		
		left = mid + 1;
		cnt++;
	}
	
	cout << total;
	
	return 0;
}

 

✨ 2트 (강의 풀이)

1 ~ 1+...+9 = 45 의 mid 값 = 23

👉 1~9까지 3개 이하의 DVD를 만들 수 있는지 체크(1부터 하나씩 더해서 23 이하로 만들 수 있는지)

👉 가능하면 다시 1 ~ 23 의 mid 값 =  12 👉 3개 초과함

👉 12~23의 mid 값을 찾아서 다시 체크하는 방식

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int a[1001], n;

int Count(int s){
	int cnt = 1, sum = 0;
	for(int i = 1; i <= n; ++i){
		if(sum + a[i] > s){
			cnt++;
			sum = a[i];
		}
		else{
			sum += a[i];
		}
	}
	
	return cnt;
}

int main(void){
	freopen("input.txt", "rt", stdin);
	
	int m, res;
    int max = -2147000000;
	cin >> n >> m;
	
	int left = 1;
	int right = 0;
	int mid;
	
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		right += a[i];
        
        if(a[i] > max){
        	max = a[i];
        }
	}
	
	while(left <= right){
		mid = (left + right) / 2;
		if(mid >= max && Count(mid) <= m){
			res = mid;
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
	
	cout << res;
	
	return 0;
}