[코드트리/C++] 한진이의 상품뽑기 (Bruteforce)

문제

https://www.codetree.ai/problems/pick-maximum-mystery-gifts/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

구상

우선, k의 상품을 넣어야 하는데, 모든 상품이 최소 m-1개씩 되도록 넣어주었고, 만일 상품이 남는다면, 마지막 종류의 상품에 상품을 몰빵해서 넣었다. 만일 상품이 부족하다면, 남은 개수를 넣어주었다. 

 

그리고 상품을 최대한 뽑는데, 우선 최대 m-1개씩 뽑는다. m-1개가 안되는 상품들은 있는 개수만큼 뽑는다. 만일, m개 이상의 상품이 있는 상품 종류가 있다면, flag = true를 통해 해당 사실을 저장해놨다가, 마지막에 flag값을 보고 true라면 1을 더해준다. 마지막 뽑기에서 한종류의 상품은 m개까지 뽑고 뽑기를 마칠 수 있기 때문이다. 

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
/*
한진이의 상품뽑기
*/

long long type, m, k;
vector<long long> nums;
long long res = 0;

void solution() {
    // k개 넣기 - (m-1)개씩 되도록. 다 주고 남는다면 나머지에 몰빵해주자
    for (long long i = 0; i < type && k > 0; i++) {
        long long can_put = (m - 1) - nums[i];
        if(can_put <= 0) continue;
        if (k >= can_put) { // 들어갈 수 있는게 남은 것보다 더 작다면
            nums[i] += can_put;
            k = k - can_put;
        } else { // 들어갈 수 있는게 k보다 더 크다면
            nums[i] += k; // k까지밖에 못 넣음
            k = 0;
        }
    }

    if (k > 0) { // 마지막에 몰빵
        nums[type - 1] += k;
    }

    sort(nums.begin(), nums.end());

    // 상품 개수 계산
    bool flag = 0;
    for (long long i = 0; i < type; i++) {
        if (nums[i] < m) {
            res += nums[i];
        } else if(nums[i] >= m) {
            flag = 1;
            res += m-1;
        }
    }
    if (flag) res++;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> type >> m >> k;

    nums.resize(type);

    for (long long i = 0; i < type; i++) {
        cin >> nums[i];
    }

    sort(nums.begin(), nums.end()); // 오름차순 정렬

    // 로직
    solution();

    cout << res;
    return 0;
}