BOJ 2437 저울 / BOJ 1339 단어 수학 / BOJ 1202 보석 도둑 (그리디)

푼 사람 수가 많은 그리디 문제들 중에서, Solved.ac 기준 Gold 티어 이상의 그리디 문제들을 풀이해보았습니다.

 

 

백준 BOJ 2437번 : 저울

N개의 추의 무게가 주어졌을 때 자연수 무게 중 측정할 수 없는 가장 작은 무게를 구하는 문제입니다.

 

문제를 처음에 보았을 때는 백준 BOJ 2629번 : 양팔저울 문제가 생각이 났습니다.

↓ 풀이는 아래에 있으며, 간략히 설명하자면 dp + 재귀적 탐색으로 풀이하는 문제입니다.

 

[백준/BOJ] 2629번 : 양팔저울, 2293번 : 동전 1, 7579번 : 앱 (DP, 동적 계획법 중급)

 

하지만 물건은 물건 쪽에만, 추는 추를 놓는 쪽에만 놓을 수 있으므로 3가지 이상의 연산이 필요하거나 하지는 않기 때문에 재귀적인 탐색은 필요하지 않습니다.

조금 생각해보면 추를 오름차순 정렬한뒤 1 ~ K번째 추들을 가지고 K+1번째 추의 무게 미만의 모든 무게들을 만들지 못한다면 sum(1 ~ K번째 추의 무게) + 1의 무게가 답이 된다는 성질을 발견할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;

    vector<int> weight(N);
    for(int i=0; i<N; i++) cin >> weight[i];

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

    int sum = 0;
    for(int i=0; i<N; i++) {
        if(weight[i] > sum + 1) break;

        sum += weight[i];
    }

    cout << sum + 1;
}

 

 

백준 BOJ 1339번 : 단어 수학

10개 이하의 수가 복면산과 같이 알파벳의 형태로 주어졌을 때, 같은 알파벳에 같은 숫자를 대입하여 N개의 수를 합한 값의 최댓값을 구하는 문제입니다.

처음에는 알파벳의 종류가 10개 이하라고 하였으니 완전 탐색을 해야하나라고 생각하였는데, 알파벳끼리 모아서 (예를 들어 A에 대해서 sum을 구한다고 할 때 ABA면 101, CAAB면 110과 같이) 합해준 값들을 정렬하고, 큰 것부터 9, 8, 7, ...을 대입해주면 되는 그리디 문제였습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

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

    int N; cin >> N;

    int sum[26] = {};
    while(N--) {
        string str; cin >> str;

        int temp = 1;
        for(int j=str.length()-1; j>=0; j--) {
            sum[str[j] - 'A'] += temp;
            temp *= 10;
        }
    }

    sort(sum, sum+26, greater<int>());

    int ans = 0;
    for(int i=0; i<10; i++)
        ans += sum[i] * (9 - i);

    cout << ans;
}

 

 

백준 BOJ 1202번 : 보석 도둑

K개의 가방 각각에 N개의 보석들 중 최대 1개씩을 넣을 수 있다고 할 때, 가장 가치가 높도록 가져갈 수 있는 보석들의 조합의 가치를 구하는 문제입니다.

 

해결책으로 두 가지의 경우의 수를 생각할 수 있습니다.

(1) 큰 가방부터 넣을 수 있는 가장 비싼 보석으로 채우기

(2) 작은 가방부터 넣을 수 있는 가장 비싼 보석으로 채우기

 

(1)의 경우에는 무게가 작지만 비싼 보석이 먼저 채워지면 뒤로 갈수록 용량이 작은 가방에 넣을 수 있는 보석들이 많지 않아집니다.

따라서 보석의 가치를 합산한 결과가 최대가 아닐 수도 있습니다.

그렇기 때문에 남은 경우인 (2)의 방법으로 보석을 채워주는 방식을 통해 정답 처리를 받을 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

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

    int N, K; cin >> N >> K;

    vector<pair<int, int>> jewel(N);
    for(int i=0; i<N; i++)
        cin >> jewel[i].first >> jewel[i].second;

    vector<int> bag(K);
    for(int i=0; i<K; i++) cin >> bag[i];

    sort(jewel.begin(), jewel.end());
    sort(bag.begin(), bag.end());

    long long ans = 0;
    int j = 0;
    priority_queue<int> pQueue;

    for(int i=0; i<K; i++) {
        while(j < N && jewel[j].first <= bag[i]) {
            pQueue.push(jewel[j].second);
            j++;
        }

        if(!pQueue.empty()) {
            ans += pQueue.top();
            pQueue.pop();
        }
    }

    cout << ans;
}

 

구현 자체는 우선순위 큐를 활용해주는 것이 편합니다.

작은 가방부터 순서대로 검사하면서 bag[i]보다 작거나 같은 (bag[i] >= jewel[j].first)들에 대해 보석의 가치(jewel[j].second)를 priority Queue에 넣어주고, top에 있는 하나만 pop 해서 답에 합산해주는 방식을 반복해주면 됩니다.