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

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

16206번: 롤케이크

개인적으로 어려웠던 분할 정복 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

 n만큼 롤케이크의 길이를 입력시 10으로 나눠떨어지는것은 ten에, 아닌 것은 notTen에 push_back했습니다.

 

📔 풀이과정

여러 경우를 나누어 생각해볼 수 있습니다.

 1. 롤케이크 길이가 10인경우 : 자를 필요가 없습니다. ans를 더해줍니다.

 2. 롤케이크 길이가 10보다 작은경우 : 이 또한 자를 필요가 없습니다. 

 3. 롤케이크 길이가 10초과며 10으로 나누어 떨어지는 경우 : 딱 10으로 나누어 떨어졌을 때 길이 / 10 - 1만큼만 자르면 길이 / 10만큼의 10짜리 조각들을 얻을 수 있습니다. 

 4. 롤케이크 길이가 10초과며 10으로 나누어 떨어지지 않는 경우 : 이 경우에는 길이 / 10만큼 잘라야 길이 / 10만큼의 10짜리 조각들을 얻을 수 있습니다.

 

이렇게 복잡하게 if else문으로 해결할 수 있지만 구현하기 어렵습니다. 따라서 분할정복으로 해결했습니다.

cutCake라는 재귀함수를 구현합니다. 이는 다음과 같이 동작합니다.

1. m이 0이하거나 롤케잌 길이가 10미만이면 return;

2. 10이상이면 계속 10씩 빼면서 ans++, m--;

3. 10을 빼도 10보다 많이 남았다면 다시 cutCake함수 호출

4. 아니라면 길이가 딱 10일 경우 ans++

 

이를 아까 10으로 나누어 떨어지는 길이들이 저장된 vector ten과 나누어떨어지지 않았을 때 길이들이 저장된 vector notTen에 대해 상기 함수를 시행합니다. 단 ten에 들어있는 원소들의 경우 딱 10일 때는 자를 필요가 없기 때문에 이부분만 예외로 처리합니다.

 

📔 정답출력

 

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
vector <int> ten, notTen;

void cutCake(int length){
    if(m <= 0 || length < 10) return;
    length -= 10;
    ans++;
    m--;
    if (length > 10) cutCake(length);
    else if (length == 10) ans++;
    return;
}

int main(){
    cin >> n >> m;
    for(int i = 0,x; i < n; i++) {
        cin >> x;
        if(x % 10) notTen.push_back(x);
        else ten.push_back(x);
    }

    sort(notTen.begin(),notTen.end());
    sort(ten.begin(),ten.end());

    for(auto t : ten){
        if(t == 10) ans++;
        else cutCake(t);
    }

    for(auto nt : notTen) cutCake(nt);
    cout << ans << '\n';
}

 

📕 TestCase

몇 가지 케이스를 작성해 봤습니다.

 

4 2
18 28 30 40
3

4 2
28 18 40 30
3

3 2
18 19 20
3