[백준/c++] BJO 26215 - 눈 치우기

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

26215번: 눈 치우기

 

문제 설명

집의 수 N이 주어진다. 각각의 집 앞에는 눈이 쌓여 있다. 집 앞에 눈을 치우려고 하는데, 눈을 치울 때는 한번에 두 집을 선택하여 각각 1만큼 치우거나 한 집을 선택해서 그 집만 1만큼 치울 수 있다.

눈을 전부 치울 때까지 걸리는 최소 시간은? 단, 24시간 (1440분)이 넘게 걸릴 경우, -1을 출력한다.

N (1 <= N <= 100)

눈의 양 a (1 <= a <= 2000)

 

해결

눈을 최소 시간 안에 치워야 하므로, 당연히 한집만 골라서 치우는 것보다 두 집을 골라 치우는 것이 이득이다.

눈이 가장 많은 집과 두번째로 많은 집을 선택해 두 집을 동시에 치운다.

두번째로 많은 집이 존재하지 않는다면, 눈이 쌓인 유일한 집만 눈을 치우면 된다.

 

1440분이 넘어가는 경우는 예외로 빼 주었다.

 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n;
vector<int> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}

	if (n == 1) {
		if (v[0] <= 1440) {
			cout << v[0];
			return 0;
		}
		cout << "-1";
		return 0;
	}

	int ans = 0;
	while (1) {
		sort(v.begin(), v.end());

		if (v[n - 1] == 0) break;

		v[n - 1]--;
		if (v[n - 2]) v[n - 2]--;
		ans++;

		if (ans > 1440) {
			cout << "-1";
			return 0;
		}
	}
	cout << ans;
}