BOJ(단어수학)(1339)

작성일 | In
  • 단어수학 0부터 9까지의 수를 알파벳 하나로 나타낸 것
  • GCF + ACDEB가 문제라고 한다면
  • 각각의 알파벳은 0123456789 중에서 하나를 의미한다.
  • 그런데 각각의 알파벳이 어떤 수를 의미하는지는 주어지지 않는다.
  • 각각의 알파벳에 적절히 수를 대응시켜, 식의 결과를 최대로 만드는 문제이다.
  • 서로 다른 알파벳의 개수는 10개이다.

풀이방법

  • GCF ABCDE의 알파벳 개수는 총 7개다.
  • 최댓값을 구할 때, 9876543, 7개의 큰 수만 있으면 된다.
  • 최댓값을 구하기 위해서는 큰 알파벳의 개수만큼만 수를 미리 골라두면 된다.
  • 먼저 알파벳을 고른 뒤, 9876543을 모든 순열을 만들어서, 각각의 알파벳이 어떤 숫자에 대응하는지 넣어보면 된다.
def next_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] <= a[i-1]:
        j -= 1

    a[i-1],a[j] = a[j],a[i-1]

    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

    return True

def calc(a, letters, d):
    m = len(letters)
    ans = 0
    alpha = dict()
    for i in range(m):
        alpha[letters[i]] = d[i]
    for s in a:
        now = 0
        for x in s:
            now = now * 10 + alpha[x]
        ans += now
    return ans
n = int(input())
a = ['']*n
letters = set()
for i in range(n):
    a[i] = input()
    letters |= set(a[i])
letters = list(letters)
m = len(letters)
d = [i for i in range(9, 9-m, -1)]
d.sort()
ans = 0
while True:
    now = calc(a, letters, d)
    if ans < now:
        ans = now
    if not next_permutation(d):
        break
print(ans)

N = int(input())
num = [0] * 26
i = 0
while i < N:
    for j, c in enumerate(input()[::-1]):
        num[ord(c)-ord('A')] += (10**j)
    i += 1
num.sort(reverse=True)
result = 0
for i in range(10):
    if num[i]:
        result += (num[i] * (9-i))
print(result)

참고자료 codeplus homebody님블로그

0%