문제

문제 링크

해설

• 문제가 조금 너무할 정도로 이상하게 해석돼있습니다. 다시 정리해서 적으면 다음과 같습니다.

  현우는 용돈을 효율적으로 활용하고, 돈을 펑펑 쓰지 않기 위해서 앞으로 N일 동안 자신이 매일 사용할 금액을 계산하고, 정확히 통장에서 M번, K원 씩 출금해서 사용하기로 결정했습니다. 현재 수중에 있는 돈으로 하루를 보낼 수 있으면 그대로 사용합니다. 하지만, 부족하다면, 수중에 있는 돈은 통장에 집어넣은 뒤 K원을 인출해서 사용할 것입니다. 이때 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성해주세요.

• 문제를 조금 바꿔보면, N개의 요소를 합이 K 미만의 M개의 그룹으로 나눌 수 있는지 여부를 계산하는 문제입니다.
  • 가장 쉬운 방법은 뭘까요? O(N × K) 풀이방법이 있을 것입니다.
  • 금액 1원부터 10,000원까지 반복문을 돌면서, N개의 요소를 M개의 그룹으로 나눌 수 있는지 여부를 계산하고, 가장 먼저 M개를 만들 수 있다면 그 때의 금액이 최솟값일 것입니다.
  • 그러나, N이 최대 10만, K가 최대 1만이므로, 최악의 경우 10억가지를 탐색해야 합니다.
• 조금 더 효율적인 방법으로는 이분탐색이 있습니다.
  • 어차피 1원부터 10,000원까지 탐색할 것이라면, 먼저 5,000원으로 검사합니다.
  • 5,000원으로 계산해보니 그룹 수가 M개보다 적다면, 너무 금액이 큰 것이므로 금액을 줄입니다.
  • 계산하다보니 M개보다 많다면, 너무 금액이 적은 것이므로 금액을 늘립니다.
• 두 번째 방법을 사용하면 O(Nlog₂K)로 시간내에 충분히 문제를 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int N, M, K, arr[100'001];
int low, mid, high, maxMoney, ans;

bool isAvailale(int target) {
	// 하루를 살기에는 금액이 너무 작음.
	if (maxMoney > target) return false;
	
	int cnt = 1, curMoney = target;
	for (int i = 0; i < N; ++i) {
		if (curMoney >= arr[i]) curMoney -= arr[i];
		else curMoney = target - arr[i], cnt++;
	}
	return cnt <= M;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
		high += arr[i];
		maxMoney = max(maxMoney, arr[i]);
	}
	while (low <= high) {
		mid = low + (high - low) / 2;
		if (isAvailale(mid)) high = mid - 1, ans = mid;
		else low = mid + 1;
	}
	cout << ans;
}

소스코드 링크

결과