[백준 22953번] 도도의 음식 준비 (C++)

https://www.acmicpc.net/problem/22953

22953번: 도도의 음식 준비

 

다른 골드4의 매개변수 탐색보다 많이 까다로운 문제다.

---

값의 범위가 작기 때문에 브루트 포스를 의심하는 것이 첫 번째 단계다.

도도가 요리사에게 격려를 해줄 수 있는 모든 경우의 수를 나이브하게 따져도 10의 6승이고, 각각의 경우에 매개변수 탐색은 log2(10^6 * 10^6)  이므로 시간적으로 10의 8승안에는 충분히 해결할 수 있다.

 

구현도 쉽지 않다. 요리사에게 격려를 해줄 수 있는 경우를 백트래킹으로 따져주고, 모든 케이스에 이분탐색을 넣어주면 된다. (백트래킹이 익숙치 않아서 더 어렵게 느껴졌다.)

추가로 더 이상 격려를 해줄 수 없는 경우도 생각해야 한다.

 

trial함수에서 for문의 시작 값을 어떻게 조정하느냐에 따라 시간이 많이 차이난다.

재귀가 돌아가는 형태가 요리사1을 포함하는 경우를 전부 따지고, 요리사2를 포함하는 경우를 따지고 ... 이런식으로 가기 때문에 반복문을 굳이 항상 0부터 시작할 필요가 없다. (0부터 시작하면 불필요한 재귀가 많이 시행 됨.)

따라서 for문의 시작 값을 정하기 위해 idx변수를 추가했다.

 

#include <iostream>
#define lint long long
using namespace std;

int n, k, c;
lint ans = 1000000000000;
int arr[11];

int bi(){
	lint left = 1, right = 1000000000000;
	while(left <= right){
		lint mid = (left+right)/2;
		lint cnt = 0;
		for(int i = 0; i < n; i++){
			cnt += (mid/arr[i]);
		}
		if(cnt >= k){
			right = mid - 1;
			ans = min(ans, mid);
		}
		else {
			left = mid + 1;
		}
	}
	return 0;
}

void trial(int cnt, int idx = 0){
	if(!cnt){
		bi();
		return;
	}
	for(int i = idx; i < n; i++){
		if(arr[i] > 1){
			arr[i]--;
			trial(cnt-1, i);
			arr[i]++;
		}
		else {
			trial(cnt-1, i);
		}
	}
}

int main() {
	cin >> n >> k >> c;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	trial(c);
	cout << ans;
}

 

 

처음 풀 때는 trial함수의 시작점을 그냥 0으로 잡고 무지성 브루트포스를 돌렸는데, 시간이 훨씬 적게 든 사람들의 코드를 참고하니 반복문의 시작 값을 조정하므로써 불필요한 재귀를 없앴더라.