백준 1339번 - 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

코드포스 만년 초록 따리를 벗어나기 위해 그리디 문제를 많이 풀어봐야겠다고 마음먹었다.

 

이 문제의 풀이는 다음과 같다.

 

1. 모든 단어에서 각 문자가 얼마만큼의 계수를 갖는지를 구하기 ex) AB이면 10A + B, 즉 A = 10, B = 1을 저장

2. 계수가 큰 알파벳 순으로 정렬 (어차피 전체 단어의 합이기 때문에 계수가 크면 큰 수를 할당해야 한다.)

3. 정렬된 알파벳에 9부터 순서대로 할당하여 합을 구하기

 

물론 대부분 브루트포스가 떠올랐겠지만 이상하게 나는 이 문제를 브루트포스로 풀기 싫었다.

 

어쨌든 그리디 알고리즘을 증명하려면 굉장히 어렵기 때문에 대충만 살펴보면

 

문제에서 모든 단어의 합이기 때문에 이를 숫자라 생각해보면 결국 문자열이 포함된 합으로 나타낼 수 있다.

 

이게 뭔 소린가 하면

 

예를 들어 "ACDEF"와 "GCF" 두 문자열을 합하여야 한다고 하자.

이를 문자열이 포함된 합으로 나타내 보면

 

10000*A + 1010C + 100D + 10E + 2F로 나타낼 수 있다.

 

결국 계수가 큰 문자부터 가장 큰 수(9)를 할당해야 하는 것은 너무나도 당연한 것이다.

 

만약 계수가 같다면? 사실 이것도 문제가 되지 않는다.

 

결국 모든 총합에서 같은 비중을 차지하기 때문에 두 수는 연속된 수를 할당하면 된다. 

이는 정렬 때문에 알아서 연속된 수가 배정되게 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, char>pic;
 
int alpha[26];
 
int main() {
    int n;
    string str;
    vector<pic>s;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str;
        int mul = 1;
        for (int k = str.size() - 1; k >= 0; k--) {
            alpha[str[k] - 'A'] += mul;
            mul *= 10;
        }
    }
    for (int i = 0; i < 26; i++) {
        if (alpha[i] != 0)s.push_back(pic(alpha[i], i + 'A'));
    }
    sort(s.begin(), s.end(), greater<pic>()); 
    int mul = 9, ans = 0;
    for (int i = 0; i < s.size(); i++) {
        ans += (s[i].first * mul--);
    }
    cout << ans << "\n";
}

 

쉽게 생각하면 더욱 쉽게 풀리는 전형적인 그리디 스타일의 문제였다.

 

근데 이게 왜 골드 4 수준의 문제인지는 잘...