BOJ 16206 롤케이크

hywn·2021년 1월 10일
0

알고리즘 연습

목록 보기
1/2
post-thumbnail

알고리즘

Greedy

풀이

  • 처리 순서 – 긴 것부터 또는 짧은 것부터
  • 주어진 길이가 10의 배수가 아닐 경우
  • 10의 배수인 것과 10의 배수가 아닌 것의 순서

주어진 테스트 케이스로 고려해 본 결과, 10의 배수인 것이 10의 배수가 아닌 것 보다 더 앞서 처리되어야 하고, 10의 배수인 것이 짧은 것부터 순서대로 처리되어야 하며, 10의 배수가 아닌 경우에는 길고 짧음의 순서가 상관 없음을 알 수 있었다.

코드

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

int n, m, len, ans;

void cut(int e) {
    if (m <= 0) return;
    else {
        e -= 10;
        ans++, m--;
        if (e > 10) cut(e);
        else if (e == 10) ans++;
        return;
    }
} 

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    vector<int> v;
    vector<int> v2;

    for (int i = 0; i < n; i++) {
        cin >> len;
        if (len < 10) continue;
        v.push_back(len);
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        if (m <= 0) break;
        else if (v[i] == 10) ans++;
        else if(v[i] % 10 == 0) cut(v[i]);
        else v2.push_back(v[i]);
    }
    
    for (int i = 0; i < v2.size(); i++) cut(v2[i]);

    cout << ans;
    return 0;
}

0개의 댓글