[BOJ/C++] 자유 이용권 - 25635번 / CPP 풀이

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

25635번: 자유 이용권

 

 

N개의 놀이기구가 있다.

각각의 놀이기구에는 이용 가능 횟수가 적혀있고 자유이용권을 가지고 최대한 많은 놀이기구를 이용하고 싶다.
단, 각각의 놀이기구는 연속으로 이용할 수 없다.

 

N개의 놀이기구를 모두 이용하는 조건은 (이용 가능 횟수가 가장 많은 놀이기구 -1)이 나머지 놀이기구의 이용횟수들 보다 작거나 같아야 한다.

 

즉, (나머지 횟수) >= (제일 횟수가 많은 기구 -1)이 되어야 이용 횟수를 남김없이 이용할 수 있다.

증명은 테케 만들어서 노가다 해보면 알 수 있음

 

그 외의 경우에는 최고 횟수 놀이기구와 (total-최고횟수)를 하나씩 빼며 최고 횟수 놀이기구가 0이 될 때 까지 횟수를 count해준다.

 

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

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long n; cin >> n;

	vector <long long> vec;
	long long maxN = -999;
	long long total = 0;

	for (long long i = 0; i < n; i++) {
		long long c; cin >> c;
		vec.push_back(c);
		maxN = max(maxN, c);
		total += c;
	}

	total = total - maxN;

	if (total >= maxN - 1) {
		cout << total + maxN;
	}
	else {
		long long tmpTotal = total;
		long long tmpMax = maxN;
		long long cnt = 0;
		long long i = 0;
		while (total && maxN) {
			if (i % 2 == 0)
				maxN--;
			else
				total--;
			cnt++;
			i++;
		}

		if (total == 0 && maxN > 0) {
			cnt++;
		}
		cout << cnt;
	}

}

 

else문에 들어오면 모든 횟수를 이용할 수 없는 경우이므로 무조건 다른 놀이기구를 마지막으로 이용하게 된다.

그러므로 둘 다 0이 된 경우가 아니라면 마지막으로 최대 횟수 놀이기구를 한 번 더 이용해주어 최대 횟수를 맞춘다.

ex) maxN = 5, total = 3일 경우

이용 순서 = maxN - total - maxN - total - maxN - total (종료) - maxN