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

문제

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

 

문제 내용

롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만드는 문제이다.

 

문제 풀이

Q) 롤케이크의 길이가 [10,34,20,14,20]이고, 자를 수 있는 횟수가 2번이라면 어떻게 해야 할까?

 

1) 그냥 정렬한 뒤에 순서대로 자른다.

- 먼저 정렬하면 [10,14,20,20,34]가 된다.
여기서 10은 칼질하지 않아도 되고, 14는 한번, 20도 한 번의 칼질이 필요하므로 10 / 14(10,4) / 20(10,10)으로 총 4개의 길이가 10인 롤케이크가 나온다.

 

2) 정렬을 하긴 하되, 10 단위의 롤케이크 부터 먼저 처리하는 경우

- 10단위의 길이가 먼저 오도록 정렬을 하면 [10,20,20,14,34]가 된다.
여기서 10은 칼질하지 않아도 되고, 20은 한 번의 칼질이 필요하므로 10 / 20(10,10) / 20(10,10)으로 총 5개의 길이가 10인 롤케이크가 나온다.

 

=> 즉, 우리는 그냥 정렬하는 것이 아니라 10 단위의 롤케이크부터 먼저 처리해야 한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, a,b, num, tmp;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
    //입력
	cin >> n >> m; //롤케이크 개수, 자를 수 있는 횟수
	vector<int>v1; //롤케이크 길이 == 10의 배수
	vector<int>v2; //롤케이크 길이 == 10의 배수가 아닌 것

	num = 0; //개수 카운트
	for (int i = 0; i < n; i++) {
		cin >> a;
		if (a < 10) continue; // 10보다 작으면 필요 없음
		else if (a == 10) num++; //길이가 10이면 처리가 필요하지 않고 그냥 +1하기
		else if (a % 10 == 0) v1.push_back(a); //길이가 10의 배수
		else v2.push_back(a); //길이가 10의 배수가 아닌 경우
	}
    
    //문제 해결
	sort(v1.begin(), v1.end()); //정렬
	sort(v2.begin(), v2.end()); //정렬

	v1.insert(v1.end(), v2.begin(), v2.end()); //두 벡터를 합치기

	while (m>0 && !v1.empty()) {
		tmp = v1[0];
		b = tmp / 10; //길이가 10인 롤케이크가 몇개 나오는지
		if (tmp % 10 == 0) { //10의 배수일 때
			if (b - 1 <= m) { //칼질 횟수 판단
				num += b;
				m -= (b - 1);
			}
			else {
				num += m;
				break;
			}
		}
		else { //10의 배수가 아닐 때
			if (b <= m) {//칼질 횟수 판단
				num += b;
				m -= b;
			}
			else {
				num += m;
				break;
			}
		}
		v1.erase(v1.begin());
	}
	
    //결과 출력
	cout << num << '\n';	
}

 

문제 코드 설명

1) 입력

먼저 롤케이크 개수 N과 칼질 횟수 M을 입력받는다. 이후 롤케이크 개수를 입력받는데, 10의 배수인 롤케이크와 그렇지 않은 롤케이크를 구분하여 저장한다.

 

2) 문제 해결

각각을 정렬하여 두 배열을 이으면, 위에서 설명한 것처럼 10 단위의 롤케이크부터 처리할 수 있게 된다.
이후 칼질 횟수가 남아있고, 처리할 롤케이크가 남아있을 때만 반복문을 돌면 된다.

길이가 30인 롤케이크가 있고 칼질 횟수가 1번만 남아있다면 결국 길이가 10인 롤케이크는 1개만 나오게 된다. 그렇기 때문에 길이와 칼질 횟수를 잘 비교해서 처리해야 한다.