[백준/BOJ] 15703. 주사위 쌓기 [Gold 4]

15703. 주사위 쌓기

문제출처 : https://www.acmicpc.net/problem/15703

code)

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

int main()
{
	int N, answer = 0, height = 0;
	bool flag, newtower;
	cin >> N;
	vector<int> dice(N);
	for (int i = 0; i < N; i++)
		cin >> dice[i];

	sort(dice.begin(), dice.end());

	int n = N;
	newtower = true;
	while (n)
	{
		flag = false;
		for (int i = 0; i < N; i++)
		{
			if (dice[i] == 1001)
				continue;
			if (dice[i] != 1001 && dice[i] >= height)
			{
				if (newtower)
					answer++;
				newtower = false;
				dice[i] = 1001;
				n--;
				height++;
				flag = true;
			}
		}
		if (flag == false)
		{
			height = 0;
			newtower = true;
		}
		sort(dice.begin(), dice.end());
	}

	cout << answer;

	return 0;
}

내림차순으로 정렬해버리면 크기순서대로 쌓아버리기 때문에 최소개수가 나오지 않는다. 그래서 오름차순으로 정렬해서 높이를 비교해가며 쌓아야한다.

근데, 중간중간에 정렬을 안해주면 시간초과가 나기때문에 정렬을 해주면서 검색을 해야한다.