[그리디] 백준 1339번: 단어 수학

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

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

import collections
n = int(input())

dct = collections.defaultdict(int)

for i in range(n):
    s = input()
    r = 10**(len(s)-1)
    for j in range(len(s)):
        dct[s[j]] += r
        r /= 10

table = []
for key, val in dct.items():
    table.append(val)

table.sort(reverse=True)

max = 9
answer = 0
for i in range(len(table)):
    answer += table[i]*max
    max-=1
print(int(answer))

처음 보고 읭? 했지만 좀만 생각해보면 쉽게 풀 수 있는 그리디 문제다.

숫자들이 막 더해지면 자릿수가 올라갈 수도 있고, 또 알파벳은 한번만 등장하는 것도 아니고

이런 생각들을 하다보니 처음에는 감이 안잡혔지만

2 GCF ACDEB를 좀 생각해보면 다음과 같아진다.

10000A + 1010C + 100D + 100G + 10E + B + F

즉 알파벳의 계수를 구한 뒤에 계수 순으로 차례대로 9,8,7,6...을 넣어주면

합이 최대가 될 것이다. 끝!