[BOJ] 백준 1339 단어 수학 c++ (그리디)

문제 출처 : https://www.acmicpc.net/problem/1339

1339번: 단어 수학

---

풀이

알파벳을 숫자로 치환했을때, 주어진 단어의 합의 최댓값을 구하는 문제이다.

 

브루트포스 방식으로 모든 숫자를 대입(dfs)해 정답을 구하는 방식도 있으나,

그리디 알고리즘으로 정답을 구하는 방법이 빠르다.

---

그리디 알고리즘 + @?

그렇다면 어떤 방식으로 해결해야 할까?

단순히 큰 자리수에 큰 숫자를 대입한다고 생각하면 아래와 같은 상황에서는 처리할 방법이 애매해진다.

ABCDE

BABCD

 

따라서 알파벳마다 해당자리 수를 곱해서 더한 값을 가중치로 생각하면 된다.

예를 들어 ABAC가 있을때

C = 1 * C

B = 100 * B

A = 10 * A + 1000 * A = 1010 A 인 것이다.

for(int i = 0; i < v.size(); i++){
    int pow = 1;
    for(int j = v[i].size() - 1; j >= 0; j--){
        int val = v[i][j] - 'A';
        alpha[val] += pow;
        pow *= 10;
    }
}
sort(alpha, alpha + 26);

위 코드를 보면, 가장 낮은 자리수부터 해당 알파벳 배열의 가중치를 더해주는 것을 확인할 수 있다.

그 후 가중치별로 우선순위를 매기므로 정렬하면 된다.

 

이제 우선순위별로 9부터 차례대로 값을 부여하면 된다.

정렬을 했으므로, 알파벳 배열의 요소가 0이면 해당 알파벳이 없다는 의미이다.

부여한 값에 가중치를 곱해 결과에 더해주면 된다.

int num = 9;
for(int i = 25; i >= 0; i--){
    if(!alpha[i]) break;
    res += (alpha[i] * num);
    num--;
}

---

코드

#include <bits/stdc++.h>

using namespace std;

int res;
int alpha[26];

bool comp(string a, string b){
    return a.length() > b.length();
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N;
    cin >> N;
    vector<string> v(N);
    for(int i = 0; i < N; i++)
        cin >> v[i];
    
    for(int i = 0; i < v.size(); i++){
        int pow = 1;
        for(int j = v[i].size() - 1; j >= 0; j--){
            int val = v[i][j] - 'A';
            alpha[val] += pow;
            pow *= 10;
        }
    }
    sort(alpha, alpha + 26);

    int num = 9;
    for(int i = 25; i >= 0; i--){
        if(!alpha[i]) break;
        res += (alpha[i] * num);
        num--;
    }
    cout << res << '\n';
	return 0;
}