백준 - 16206번 : 롤케이크 (C++)

풀이 방법 : 그리디

M번 자를 수 있을 때 길이 10인 케이크 개수의 최댓값을 구하는문제다. 길이가 10으로 나누어떨어지는 케이크들을 우선적으로 잘라서 개수를 구하고 그 뒤에 다른 케이크들을 잘라야한다.
-> 길이가 26이라면 2번 잘라야만 길이가 10인 케이크가 두 개 나오지만 길이가 20이라면 1번만 자르면 케이크가 2개 나오기 때문이다.

1. 먼저 입력을 받을 때 케이크의 길이가 10 미만이면 따져볼 필요도 없다. 이어붙이는게 아니므로 버려줬다.

2. 딱 10인 케이크는 자를 필요도 없이 이미 10이므로 버리고 롤케이크의 수만 늘려줬다.

3. 이후로 10으로 나누어떨어지는지에 따라 케이크의 길이값들을 따로 저장해주었다.

4. 10으로 나누어떨어지는 케이크들은 오름차순으로 정렬하여 따져줘야한다.
   만약 자르는 횟수가 2번만 남아있다고 치고, 길이가 30인 케이크와 80인 케이크가 남아있다고 쳐보자 30을 두 번 자르면 케이크가 길이 10인 케이크가 3개가 나오지만 80인 케이크를 두 번 자르면 10, 10, 60으로 나뉘어져 2개밖에 나오지 않기 때문이다.
   즉 케이크의 길이가 (남은 횟수) * 10이하인 경우 (N-1)번의 커팅으로 N개의 케이크를 만들어낼 수 있기 때문이다.

5. 10으로 나누어떨어지는 케이크들을 다 처리해줬음에도 자르는 횟수가 남아있다면 다른 케이크들을 처리해주면 된다. 이 케이크들은 어차피 10인 케이크를 N개 만드는데 N번의 커팅이 필요하므로 따로 정렬을 해줄 필요는 없다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;


	vector<int> vecTenCake;
	vector<int> vecCake;
	int SumCnt = 0;

	for (int i = 0; i < N; ++i)
	{
		int Cake;
		cin >> Cake;

		if (Cake > 10)
		{
			if (Cake % 10 == 0)
				vecTenCake.push_back(Cake);

			else
				vecCake.push_back(Cake);
		}

		else if(Cake == 10)
		{
			++SumCnt;
		}
	}

	int Idx = 0;

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

	while (M > 0)
	{
		if (vecTenCake.size() <= Idx)
			break;
		
		int Cnt = vecTenCake[Idx] / 10;
		int CutCnt = Cnt - 1;

		if (CutCnt <= M)
		{
			M -= CutCnt;
			SumCnt += Cnt;
			++Idx;
		}

		else
		{
			SumCnt += M;
			M = 0;
			break;
		}
	}

	Idx = 0;
	while(M > 0)
	{
		if (vecCake.size() <= Idx)
			break;

		int Cnt = vecCake[Idx] / 10;

		if (Cnt <= M)
		{
			M -= Cnt;
			SumCnt += Cnt;
			++Idx;
		}

		else
		{
			SumCnt += M;
			M = 0;
			break;
		}

	}

	cout << SumCnt;

}