[BOJ 1339, Python 3] 단어 수학

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

1339번: 단어 수학

 

풀이

일단 이 문제는 알파벳의 개수가 최대 10개라서 10!으로 모든 경우의 수를 확인하면서 풀 수도 있습니다.

하지만 그리디로 풀려면 어떻게 풀어야할까요?

 

일단 자리수가 큰 숫자별로 9, 8, .. 숫자를 부여하는 방식을 떠올릴 수 있습니다.

하지만 이 방법은 아래와 같은 입력값이 주어지면 윗 논리대로라면 A = 9, B = 8을 넣으면 178로 최댓값이겠지만, 실제로는 A = 8, B = 9여야 179로 최댓값이 나옵니다.

10
AB
B
B
B
B
B
B
B
B
B

그러면 이런 경우를 생각해볼 수 있습니다.

각 알파벳을 따로 분리시켜서 계수 * 알파벳으로 구하는 것이죠. 만약 AB = 10 * A + B이렇게요.

위 입력값을 예시로 들면 10 * A + 11 * B가 나옵니다. 그래서 B = 9, A = 8을 대입할 수 있습니다.

이렇게 계수를 구해서 내림차순으로 만들고, 여기에 9, 8, 7, ... 숫자를 곱해주면 최댓값이 보장됩니다.

 

 

코드

n = int(input())
dfd = __import__('collections').defaultdict(lambda: 0)
for _ in range(n):
    s = input()
    for i in range(len(s)):
        dfd[s[i]] += (10 ** (len(s) - 1 - i))
ans = sum(x * (9 - i) for i, x in enumerate(sorted(dfd.values(), reverse=True)))
print(ans)