[그리디 문제풀기] Google Code Jam 2018 - Qualification Round (문제 A) (C/C++)

Code Jam - Google’s Coding Competitions

 

문제 A: 다시 우주를 구하기 (Saving The Universe Again)

↓ 문제 캡처

 

 

간략한 문제 해설

공격(Shoot)과 기 모으기(Charge)가 있다고 했을 때,
Charge 시 데미지가 2배가 되어 공격력이 높아지고, Shoot 시 높아진 공격력으로 맞게 된다. 초기 데미지는 1이다.

예를 들어 'CS'의 총 데미지는 2, 'SCCSSC'의 총 데미지는 1+4+4 = 9가 된다.

이 때 맞는 데미지를 낮추기 위해 인접한 C와 S를 바꿀 수 있고, 실드가 버틸 수 있는 한계치 D가 주어진다.
그러므로 C와 S를 최소한으로 바꾸어서 D와 같거나 더 낮은 데미지를 만들어야 한다.

입력에서 한계치 D와 공격패턴이 주어지므로, 데미지를 D와 같거나 더 작게 만드는 최소한의 패턴 변경수를 출력하면 된다.
만약 패턴을 바꿔도 그런 경우를 만들 수 없다면 'IMPOSSIBLE'을 출력한다.

 

핵심 알고리즘

처음에 각 S에서의 데미지를 저장하고, 총 교체 가능 횟수만큼 제일 큰 숫자를 2로 나누면 된다.
각 S에서 보면 왼쪽에 있는 C의 개수만큼 자리를 바꿀 수 있으므로, 총 교체 가능 횟수는 각 S의 교체 가능횟수의 합이 된다.
총 교체 가능 횟수가 소진될 때까지 데미지를 나누고, D와 같거나 작아지는 순간에 교체한 횟수를 출력하면 된다.

 

예시) 6 SCCSSC

데미지
SCCSSC
1      44

교체가능횟수
SCCSSC
        22
(∵ 총 교체가능횟수 4)

데미지 정렬 → 144
가장 큰 숫자 2로 나누기 → 1번 나누고 정렬하면 124 (총합 7) → 2번 나누고 정렬하면 122 (총합 5 => 2 출력 후 종료)

 

이를 적용해 코드를 짜면 된다.

내 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int t, d;
    string p;
    scanf("%d", &t);
    for(int i=1; i<=t; i++) {
        cin >> d >> p;
        int cntC = 0, counts = 0, damage = 1;
        vector<int> shoot;
        int len = p.length();
        // 각 S마다 왼쪽에 있는 C의 개수만큼 교체 가능
        for(int j=0; j<len; j++) {
            if (p[j]=='C') {
                damage *= 2;
                cntC++;
            } else {
                shoot.push_back(damage);
                counts += cntC;
            }
        }
        // 데미지 총합이 D와 같거나 작아질때까지
        // 교체가능횟수 소진될 때까지 shoot에 들어있는 가장 큰 damage를 2로 나누기
        int vlen = shoot.size(), sum = 0;
        for(int j=0; j<vlen; j++) {
            sum += shoot[j];
        }
        int changed = 0;
        while(counts-- && sum > d) {
            sort(shoot.begin(), shoot.end());
            shoot[vlen-1] /= 2;
            sum -= shoot[vlen-1];
            changed++;
        }
        if (sum > d) printf("Case #%d: IMPOSSIBLE\n", i);
        else printf("Case #%d: %d\n", i, changed);
    }

    return 0;
}

 

다른 사람 코드

정렬을 내림차순으로 정렬해 앞에서 꺼내썼다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> shoot;

bool compare(int a, int b) {
    return a > b;
}

int main() {
    int tc, t = 0;
    cin >> tc;
    while(t++ != tc) {
        cout << "Case #" << t << ": ";
        int d, counts = 1, damageSum = 0, cnt = 0, damage = 1;
        string p;
        cin >> d >> p;
        shoot.clear();
        for(int i=0; i<p.size(); i++) {
            if(p[i] == 'C') {
                damage *= 2, cnt++;
            } else {
                counts += cnt, damageSum += damage;
                shoot.push_back(damage);
            }
        }
        bool find = false;
        int i=0;
        while(counts--) {
            if(damageSum <= d) {
                find = true;
                cout << i << '\n';
                break;
            }
            sort(shoot.begin(), shoot.end(), compare);
            damageSum -= shoot[0] / 2;
            shoot[0] /= 2;
            i++;
        }
        if(!find) cout << "IMPOSSIBLE" << '\n';
    }
    return 0;
}