BOJ 16401 - 과자 나눠주기

16401번: 과자 나눠주기 (acmicpc.net)

16401번: 과자 나눠주기

 

접근 방법

가장 길게 과자를 N명에게 나눠주는 문제이다.

이때 핵심이 과자를 부러뜨리면 다시 합칠 수 없다는 것이다.

 

예제 1을 보자.

 

1 2 3 4 5 6 7 8 9 10에서 3명에게 가장 긴 과자를 주려면

8 , 9 , 10을 선택하여 9와 10을 각각 1, 2 만큼 부러뜨려 8로 맞춰 주면된다.

 

예제 2번의 경우 한 번더 생각해봐야한다.

 

10 10 15를 3명에게 나눠주려면 어떻게 해야할까?

 

10 10 7 8 로 나누 후, 가장 낮은 길이인 7로 맞춰 주면된다.

 

과자는 얼마의 길이든지 부실 수 있기 때문에, 우리는 과자를 n개로 나눠야한다.

이때 무엇을 기준으로 n개로 맞출 것인가라고 할때, 과자의 길이를 중심으로 맞추면된다.

 

이게 무슨 소리이냐면

만약 과자의 길이가 7일 때, N개로 나눌 수 없다면 과자의 길이는 1~6까지 중 하나이다.

반대로, 과자의 길이가 7일 때, N개보다 많거나 같게 나눌 수 있다면, 답은 7~ 이다.

 

어디서 많이 본 것이 아닌가? 바로 이분탐색이다.

 

이를 이분 탐색을 이용해 매우 빠르게 해결할 수 있다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<map>

#define MAX_NUM 1000001

using namespace std;

int n, m;
int res;
vector<int> snack;


int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> n >> m;

	int maxi = 0;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		snack.push_back(tmp);
		maxi = max(maxi, tmp);
	}
	
	int l = 1, r = maxi;
	while (l <= r) {
		int mid = (l + r) / 2;
		int tmp = 0;
		
		for (int i = 0; i < m; i++) {
			tmp += snack[i] / mid;
		}

		if (tmp >= n) {
			l = mid + 1;
			res = mid;
		}
		else {
			r = mid - 1;
		}
	}

	cout << res;
}

이분 탐색으로 해결할 수 있다는 것을 파악하는데 꽤 많은 시간이 걸렸다..

이런 류의 이분탐색 문제도 있다는 것을 명심하자...