백준 16206 롤케이크

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

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

using namespace std;

vector<int> cake;

bool comp(const int a, const int b){
    if (a % 10 != b % 10) {
        return a % 10 < b % 10;
    } else {
        return a < b;
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    int ans = 0;

    cin >> n >> m;

    cake.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> cake[i];
    }

    sort(cake.begin(), cake.end(), comp);

    for (int i = 0; i < n; i++) {
        while (cake[i] > 10 && m > 0) {
            m--;
            cake[i] -= 10;
            ans++;
        }
    }

    for (int i = 0; i < n; i++) {
        if (cake[i] == 10) {
            ans++;
        }
    }

    cout << ans;

    return 0;
}

1. 문제

n개의 롤케이크의 길이가 주어진다. 이 롤케이크를 최대 m번 잘라 길이가 10인 롤케이크를 최대한 많이 만들려고 할 때, 길이 10짜리 롤케이크의 최대 개수를 구하라.

2. 풀이

롤케이크를 길이 10으로 자를 때 다음의 경우가 있다.

 

우선 일반적인 경우 k*10+@를 10의 단위로 자르면 k개의 롤케이크가 나온다.

롤케이크가 10으로 나누어 떨어진다면, 같은 횟수로 잘랐을 때 마지막 롤케이크도 길이가 10이므로 조건을 만족하는 롤케이크를 하나 더 만들 수 있다.

 이를 기준으로 문제를 풀 수 있다.

bool comp(const int a, const int b){
    if (a % 10 != b % 10) {
        return a % 10 < b % 10;
    } else {
        return a < b;
    }
}

sort(cake.begin(), cake.end(), comp);

입력받은 케이크를 정렬해야 하는 데, 10으로 나누어 떨어지는 롤케이크를 먼저 자르기 위해 롤케이크를 10으로 나눈 나머지의 오름차순으로 정렬한다. 만약 같다면, 두 번째 그림에서 볼 수 있듯이 10으로 나누어 떨어지는 롤케이크는 모두 잘라야 마지막의 롤케이크를 셀 수 있으므로 오름차순으로 정렬한다.

    for (int i = 0; i < n; i++) {
        while (cake[i] > 10 && m > 0) {
            m--;
            cake[i] -= 10;
            ans++;
        }
    }

횟수 m을 초과하지 않는 선에서 롤케이크가 10보다 큰 경우 10의 단위로 잘라 표현할 수 있다.

    for (int i = 0; i < n; i++) {
        if (cake[i] == 10) {
            ans++;
        }
    }

다음은 자르고 남은 롤케이크의 길이가 10인 경우를 세준다. 이 결과를 출력하면 정답을 구할 수 있다.