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

 

16206번: 롤케이크

 

단순 그리디라고 생각해서 작은 것부터 자를 수 있는 만큼 잘라나가는 식으로 했지만 실패했다.

왜 틀렸을까 생각해 보니

 

1. 길이가 20인 롤케이크는 한 번 잘라서 길이 10인 롤케이크를 2개 만들 수 있다는 점

2. 길이가 10의 배수인 롤케이크를 길이가 10으로 나누어 떨어지지 않는 롤케이크 보다 먼저 자르는 게 이득일 것이라는 점

 

이 같은 점들을 고려해서

 

1. 10으로 나누어 떨어지는 것들을 오름차순으로 앞에 오도록, 

2. 10으로 나누어 떨어지지 않는 것들은 뒤 쪽에 오름차순으로

 

정렬했다.

 

    std::sort(cake, cake + N, [&](int a, int b) {
        if ((a % 10 == 0) && (b % 10 == 0)) {
            return a < b;
        } else if ((a % 10 == 0) && (b % 10 != 0)) {
            return true;
        } else if ((a % 10 != 0) && (b % 10 == 0)) {
            return false;
        } else {
            return a < b;
        }
    });

 

이렇게 정렬하게 되면

 

5 8
34 45 20 10 30

 

이런 입력이 들어왔을 때

 

10 20 30 34 45

 

이렇게 정렬되게 된다.

 

 

이후 순차적으로 롤케이크의 길이를 검사한다.

 

1. 애초에 길이가 10이라면 정답만 1 증가하고 다음으로 넘어간다.

2. 아직 자를 수 있는 횟수가 남아있다면 10씩 자른다.

3. 자른 후에 남은 길이가 10이라면 정답을 1 증가시킨다.

 

 

코드

#include <iostream>
#include <algorithm>

int N, M;
int cake[1001];

int main() {
    std::cin >> N >> M;

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

    std::sort(cake, cake + N, [&](int a, int b) {
        if ((a % 10 == 0) && (b % 10 == 0)) {
            return a < b;
        } else if ((a % 10 == 0) && (b % 10 != 0)) {
            return true;
        } else if ((a % 10 != 0) && (b % 10 == 0)) {
            return false;
        } else {
            return a < b;
        }
    });

    int cnt = 0, cakes = 0;
    bool end = false;
    for (int i = 0; i < N; i++) {
        int length = cake[i];
        if (length == 10) {
            cakes++;
            continue;
        }
        if (end) {
            continue;
        }
        while (length > 10) {
            length -= 10;
            cakes++;
            cnt++;
            if (cnt == M) {
                end = true;
                break;
            }
        }
        if (length == 10) {
            cakes++;
        }
    }

    std::cout << cakes << "\n";

    return 0;
}