[BOJ 16206 // C++] 롤케이크

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

 

이번에 볼 문제는 백준 16206번 문제인 롤케이크이다.
문제는 아래 링크를 확인하자.

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

16206번: 롤케이크

길이가 10k(k는 양의 정수)인 롤케이크를 k-1회 쪼개면 길이 10의 롤케이크를 k개 얻을 수 있음을 관찰하자. 즉, 일반적으로는 롤케이크 쪼개기를 한 번 해서는 새로운 길이 10의 조각을 하나만 얻을 수 있지만 길이가 10의 배수인 롤케이크를 쪼갠다면 덤으로 하나의 조각을 더 얻을 수 있음을 관찰하자.

 

따라서, 길이가 짧은 길이 10의 배수의 롤케이크부터 차례대로 케이크를 쪼개나가는 것을 시도하는 것으로 문제의 답을 구해낼 수 있다.

 

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

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

int N, M;
vector<int> vec10;
int ans, cnt;

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

	cin >> N >> M;
	while (N--) {
		int x; cin >> x;
		if (x % 10) cnt += x / 10;
		else vec10.emplace_back(x);
	}

	sort(vec10.begin(), vec10.end(), greater<int>());

	while (!vec10.empty()) {
		int cur = vec10.back() / 10; vec10.pop_back();
		if (cur - 1 <= M) M -= (cur - 1), ans += cur;
		else {
			ans += M;
			M = 0;
			break;
		}
	}

	ans += min(cnt, M);

	cout << ans;
}