[BOJ] 18113 - 그르다 김가놈

1. 문제 해석

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

18113번: 그르다 김가놈

• N개의 김밥이 있다. 김밥의 양끝은 Kcm 잘라낸다.
• 김밥의 길이가 2 * Kcm보다 짧을 경우 한쪽만 자고, Kcm 이하면 버린다.
• 손질된 김밥을 Pcm 크기로 일정하게 자르려고 할 때, M개 이상의 김밥 조각을 얻을 수 있도록 하는 P의 최대값을 구해야 한다.

 

2. 접근방법

1부터 가장 긴 깁밥의 길이까지 확인하면 정답을 얻을 수 있다. 하지만 김밥의 길이가 최대 10^9이고 김밥의 개수가 최대 10^6이기 때문에 이분탐색을 이용하여 수행시간을 단축하였다.

• 입력을 통해 가장 긴 김밥의 길이를 maxLen에 저장한다.
• 1~maxLen 사이 값을 이분 탐색 진행
  • mid = (st + ed) / 2 
  • mid 값으로 M개의 김밥을 만들 수 있다면 st = mid + 1, 없다면 ed = mid - 1

 

3. 주의할 점

• 김밥의 길이가 Kcm 이하일 경우 버려야 한다.

 

4. 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, K, M;
int arr[1000001];
int ans;

bool check(int p) {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (arr[i] >= 2 * K) {
			cnt += (arr[i] - 2 * K) / p;
		}
		else if (arr[i] < 2 * K && arr[i] > K) {
			cnt += (arr[i] - K) / p;
		}
	}
	return cnt >= M;
}

void binarySearch(int st, int ed) {
	if (st > ed) return;

	int mid = (st + ed) / 2;
	if (check(mid)) {
		ans = max(ans, mid);
		binarySearch(mid + 1, ed);
	}
	else binarySearch(st, mid - 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> K >> M;
	int maxLen = 0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		maxLen = max(maxLen, arr[i]);
	}

	ans = -1;
	binarySearch(1, maxLen - K);
	cout << ans << '\n';

	return 0;
}