단어 수학 C++ - 백준 1339

https://www.acmicpc.net/problem/1339

그리디 문제.

문제 접근

합을 크게 해야 되기 때문에 모든 수를 최대한 크게 만들어야한다.

예를 들어 다음과 같은 예시가 있다고 해보자.

4
AABBC
BBAAD
AACD
ADDDD

이때는 직관적으로 A에 9를 배정해야 큰수가 나온다는 사실을 알 것이다.

그러면 어떨때 큰 수들을 배정해야 할까?

위 예시에서 A에 9를 배정한다는 것은

$2\cdot10^4+2\cdot10^3+2\cdot10^2+10^1$에 9를 곱한다는 사실과 같다.

따라서 단어에 등장한 알파벳들의 수를 체크하고 수가 큰 순서대로

큰 수를 배정하면 된다.

코드는 다음과 같다.

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

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	int ans=0;
	int ten[8]; for(int i=0;i<8;i++) ten[i]=pow(10,i); 
	int arr[26]; memset(arr,0,sizeof(arr));
	priority_queue<int> pq;
	for(int i=0;i<n;i++){
		string s; cin >> s;
		for(int i=0;i<(int)s.length();i++) arr[s[i]-'A']+=ten[s.length()-(i+1)];
	}
	for(int i=0;i<26;i++) if(arr[i]>0){pq.push(arr[i]);}
	int c=9;
    while(!pq.empty()){
		ans+=c*pq.top(); c--; pq.pop();   	
    }
    cout << ans;    
}