[이취코] 유형별 기출 - 그리디 문제(c++)

1. 모험가 길드

1, 2, 3 / 2 2 결성 돼야 하는줄알고 reserve 써서 했는데 이렇게 풀 수 있구나 ..!

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

int main() {
    int n, num;
    vector<int> v;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());  // 1 2 2 2 3

    int result = 0; // 총 그룹 수
    int cnt = 0; //현재 그룹에 포함된 모험가 수

    for (int i = 0; i < n; i++) {
        cnt++;
        if (cnt >= v[i]) {
            result++;
            cnt = 0;
        }
    }

    cout << result;
    
    //1, 2 2 그룹 
    //2, 3은 그룹결성 못함 ..
}

 

2. 곱하기 혹은 더하기

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int result = s[0] - '0';

    for (int i = 1; i < s.size(); i++) {
        int num = s[i] - '0';
        if (num == 0 || num == 1) {
            result += num;
        } else {
            result *= num;
        }
    }
    cout << result;
}

 

3. 문자열 뒤집기

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    int cnt0 = 0, cnt1 = 0; //0로 돼있는 구간, 1로 돼있는 구간
    cin >> s;
    
    if (s[0] == '0') {
        cnt0++;
    } else {
        cnt1++;
    }

    // 1로 바뀌는 경우 : 1 / 0으로 바뀌는 경우 : 2
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] != s[i + 1]) {
            if (s[i + 1] == '0') {
                cnt0++;
            } else {
                cnt1++;
            }
        }
    }

    if (cnt0 < cnt1) {
        cout << cnt0;
    } else {
        cout << cnt1;
    }
}

 

4. 만들 수 없는 금액

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

int main() {
    int n;
    vector<int> v;

    cin >> n;

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

    int target = 1;
    for (int i = 0; i < v.size(); i++) {
        if (target < v[i])
            break;
        target += v[i];
    }
    cout << target;
}

 

5. 볼링공 고르기

2차원 배열로 해도 1초라 그렇게 풀었는데 다른 좋은 방법이 있었다!

 

1 3 2 3 2

무게 1 : 2개

무게 2 : 2개

무게 3 : 2개

 

   A 선택        B 선택 

    무게 1     :   4가지 -> (1, 2), (1, 3), (1, 4), (1, 5) = (5-1)*4)

    무게 2    :   4가지 -> (3, 2), (3, 4), (5, 2), (5, 4) = (4-2)*2

    무게 3    :  0가지 = (2-2)*2

 

전체 볼링공 개수에서 현재 볼링공의 개수를 빼고, (A의 선택에 따라 B 선택의 폭이 좁아짐)

현재 볼링공의 개수를 더해준 것을 누적합하면 됨 !

#include <iostream>
using namespace std;

int arr[11];

int main() {
    int n, m, num, cnt = 0;
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        cin >> num;
        arr[num]++;
    }

    for (int i = 1; i <= m; i++) {
        n -= arr[i];
        cnt += n * arr[i];
    }

    cout << cnt;
}

 

6. 무지의 먹방 라이브

1. k가 0일 때

2. 차이를 뺄 때, 남은시간보다 차이가 클 경우

여기서 summary는 앞선 그림과 다르게 누적합으로 k랑 비교함 !

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

bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int solution(vector<int> food_times, long long k) {
    long long summary = 0;
    for (int food_time: food_times) {
        summary += food_time;
    }
    if (summary <= k) { //먹을 게 없음
        return -1;
    }

    //시간이 작은 음식부터 빼야하기 때문에 pq 사용
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < food_times.size(); i++) {
        pq.push({-food_times[i], i + 1}); //(음식 시간, 음식 번호)
    }

    summary = 0; //먹기 위해 사용한 시간
    long long pre = 0; //직전에 다 '먹은 음식' 시간
    long long length = food_times.size(); //'남은 음식'의 개수
    while (summary + ((-pq.top().first - pre) * length) <= k) { //3 -> 5 -> 6(종료)
        int now = -pq.top().first;
        pq.pop();
        summary += (now - pre) * length;
        length--;
        pre = now;
    }

    //남은 음식 중에서 '몇 번째 음식' 인지 확인해 출력 (if 남은시간 0이면, result에 하나만 들어감)
    vector<pair<int, int>> result;
    while (!pq.empty()) {
        int food_time = -pq.top().first;
        int num = pq.top().second;
        pq.pop();
        result.emplace_back(food_time, num);
    }
    sort(result.begin(), result.end(), compare); // 음식의 번호 기준으로 정렬
    return result[(k - summary) % length].second;
}

int main() {
    vector<int> food_times = {3, 1, 2};
    long long k = 5;
    cout << solution(food_times, k); //음식 번호 기준으로 정렬

    return 0;
}