1339번: 단어 수학
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대
www.acmicpc.net
그리디(탐욕 알고리즘)로 풀 수 있는 문제다. 그리디가 보통 잘 나오지 않는 편인데 그리디로 된다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int count[28];
int compare(const void *a, const void *b)
{
return *(int*)b - *(int*)a;
}
int main(){
int N;
memset(count, 0x00, sizeof(count));
scanf("%d", &N);
for(int i=0 ; i<N; ++i) {
char input[10];
scanf("%s", input);
int mul = 1;
for(int j=strlen(input)-1; j>=0; --j){
count[input[j]-'A'] += mul;
mul *= 10;
}
}
qsort(count, 27, sizeof(int), compare);
int mul = 9;
int result = 0;
for(int i=0; i<27; ++i){
if(count[i] == 0){
break;
}
else {
result += (mul * count[i]);
mul -= 1;
}
}
printf("%d\n", result);
return 0;
}