취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25635번 문제인 자유 이용권이다.
문제는 아래 링크를 확인하자.

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

먼저 놀이기구가 한 종류뿐이라면 그 유일한 놀이기구를 한 번 이용하는 것 외로는 더 이상 어떠한 놀이기구도 이용할 수 없으므로 답은 1이 된다. 아래에서는 놀이기구가 둘 이상인 상황을 생각해보자.

자유 이용권으로 이용할 수 있는 놀이기구의 이용횟수 총합을 total, 가장 많이 이용할 수 있는 놀이기구의 이용횟수를 mx라 하자. 이 때 mx가 (total+1)/2 이하인 경우, 놀이기구들을 놀이기구의 이용 가능 횟수 내림차순으로 1,3,5,...,(total 이하의 최대 홀수), 2, 4, 6, ..., (total 이하의 최대 짝수)순서대로 채워넣으면 모든 놀이기구를 항상 이용할 수 있음을 알 수 있다. 그렇지 않은 경우, 즉 mx가 (total+1)/2보다 큰 경우, mx회를 제외한 나머지 횟수(total-mx) 사이사이에 해당 놀이기구를 최대한 끼워넣어(total-mx+1) 타는 것이 놀이기구 이용횟수의 최댓값이 된다.

답이 32비트 정수 범위를 넘어갈 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

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

	ll total = 0, mx = 0;
	int N; cin >> N;
	if (N == 1) cout << 1;
	else {
		while (N--) {
			ll x; cin >> x;
			total += x, mx = max(mx, x);
		}
		if (mx <= (total + 1) / 2) cout << total;
		else cout << (total - mx) * 2 + 1;
	}
}