728x90
반응형
이 문제를 greedy로 풀었다.
알파벳 별로 자릿수를 더한 수를 구한 후 배열 내에 담는다.
ABCA
A) 1001
B) 100
C) 10
for(int i = 0; i < wordVector.size(); i++){
int powNum = 1;
for(int j = wordVector[i].size() - 1; j >= 0; j--){
word[wordVector[i][j] - 'A'] += powNum;
powNum *= 10;
}
}
그리고 알파벳 배열을 내림차순으로 정렬 후 9부터 0까지 자릿수를 더한 수와 곱하면 알파벳 수의 합을 최대로 만들 수 있다.
9009 + 800 + 70 = 9879
sort(word, word + 26, compare);
int number = 9, answer = 0;
for(int i = 0; i < 26; i++){
if(word[i] == 0) continue;
answer += word[i] * number;
number--;
}
코드는 이렇게 구현했다.
//단어 수학
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool compare(int a, int b){
return a > b;
}
int main(void){
int count;
string str;
vector<string> wordVector;
int word[26] = {0,};
cin >> count;
for(int i = 0; i < count; i++){
cin >> str;
wordVector.push_back(str);
}
for(int i = 0; i < wordVector.size(); i++){
int powNum = 1;
for(int j = wordVector[i].size() - 1; j >= 0; j--){
word[wordVector[i][j] - 'A'] += powNum;
powNum *= 10;
}
}
sort(word, word + 26, compare);
int number = 9, answer = 0;
for(int i = 0; i < 26; i++){
if(word[i] == 0) continue;
answer += word[i] * number;
number--;
}
cout << answer;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 숨바꼭질 2 (0) | 2020.11.17 |
---|---|
[algorithm] 백준 - 스타트와 링크 (0) | 2020.11.17 |
[algorithm] 백준 - 소인수분해 (0) | 2020.11.13 |
[algorithm] 백준 - 부분 수열의 합 2 (0) | 2020.11.10 |
[algorithm] 백준 - 카잉 달력 (0) | 2020.11.10 |