Codeforces Round #805 (Div. 3) - D

문제 출처:

https://codeforces.com/contest/1702/problem/D

 

문제 분석:

단어 별로 cost를 매길때

cost가 주어졌을때 이하가 되도록 글자를 그만큼 제거하고 index는 변하지 않게 출력해 내는 것이다.

 

문제 해결:

이 역시 그리디한 방식으로 풀릴것같은데 문제는 구현이였다.

priority queue를 이용해서 cost가 큰 글자부터 제거해 나가면 된다.

 

내 소스코드:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cstring>
#include <list>
#include <set>
#include <string.h>
#include <map>
#include <limits.h>
#include <stdlib.h>
#include <typeinfo>
#include <bitset>
 
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
const int INF = 987654321;
 
int testcase;
 
 
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> testcase;
 
    while (testcase--)
    {
        string tmp;
        int a;
        int sum = 0;
        cin >> tmp;
        cin >> a;
 
        priority_queue<pii> pq;
 
        for (int i = 0; i < tmp.size(); i++)
        {
            pq.push({ tmp[i] - 'a' + 1, i });
            sum += (tmp[i] - 'a' + 1);
        }
        int cost = 0;
 
        while (true)
        {
            if (a >= sum - cost)
            {
                break;
            }
 
            if (pq.empty())
                break;
 
            pii t = pq.top();
            pq.pop();
            tmp[t.second] = '~';
            cost += t.first;
 
        }
 
        for (int i = 0; i < tmp.size(); i++)
        {
            if(tmp[i] != '~')
                cout << tmp[i];
        }
        cout << "\n";
    }
 
 
    return 0;
}

 

고찰 :

priorityqueue를 생각해 내지 못해서 처음에 구현하는데 큰 어려움을 겪었었다.

이번에 E번문제에서 사람들이 많은 시간을 쓰고 풀지 못하였는데 다음에는 도전할 수 있는 실력을 가져야겠다.