[백준] 26215 눈 치우기

[백준] 26215 눈 치우기

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

• 주의해야할 테스트 케이스

input:
5
9 8 7 6 6 6
ans: 18
output: 21

틀린 풀이

• 9 8 7 6 6 (time: 0)
  0 0 6 6 6 (time: 9)
  0 0 0 0 6 (time: 15)
  0 0 0 0 0 (time: 21)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

	int n;
	cin >> n;
	
	vector<int> snows;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;

		if (input > 1440) {
			cout << -1;
			return 0;
		}
		snows.push_back(input);
	}

	//집 앞의 눈 오름차순 정렬
	sort(snows.begin(), snows.end());

	int time = 0;
	while (!snows.empty()) {

		//가장 높이 쌓인 집 앞의 눈 치우기
		int maxSnow = snows.back();
		time += snows.back();
		snows.pop_back();

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

		//이와 동시에 치울 수 있는 다른 집 앞의 눈 치우기
		while (!snows.empty()) {
			int snow = snows.back();
			snows.pop_back();
			if (snow <= maxSnow) {
				maxSnow -= snow;
				if (maxSnow == 0) break;
			}
			else {
				snows.push_back(snow - maxSnow);
				sort(snows.begin(), snows.end());
				break;
			}
		}
	}
	cout << time;
	return 0;
}

풀이

• 9 8 7 6 6 (time: 0)
  8 7 7 6 6 (time: 1)
  7 7 6 6 6 (time: 2)
  6 6 6 6 6 (time: 3)
  6 6 6 5 5 (time: 4)
  6 5 5 5 5 (time: 5)
  5 5 5 5 4 (time: 6)
  5 5 4 4 4 (time: 7)
  4 4 4 4 4 (time: 8)
  4 4 4 3 3 (time: 9)
  4 3 3 3 3 (time: 10)
  3 3 3 3 2 (time: 11)
  3 3 2 2 2 (time: 12)
  2 2 2 2 2 (time: 13)
  2 2 2 1 1 (time: 14)
  2 1 1 1 1 (time: 15)
  1 1 1 1 0 (time: 16)
  1 1 0 0 0 (time: 17)
  0 0 0 0 0 (time: 18)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

	int n;
	cin >> n;
	
	vector<int> snows;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		snows.push_back(input);
	}

	if (n == 1) {
		if (snows[0] > 1440) cout << -1;
		else cout << snows[0];
		return 0;
	}

	int time = 0;
	while (true) {
		sort(snows.begin(), snows.end());
		
		//모든 눈을 치운 경우
		if (snows[n - 1] == 0) break;

		snows[n - 1]--;
		if(snows[n - 2] != 0) snows[n - 2]--;
		time++;

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