본문 바로가기

Dev/Algorithm

[백준] 1339 - 단어수학

반응형

www.acmicpc.net/problem/1339

 

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;
}
반응형