[알고리즘][1][백준_1339][Python3] - 단어 수학

 

 

 

 

---

문제이해

이 문제의 포인트는 단어의 자릿수에 따라 해당 알파벳의 파워가 달라진다는 것이다.

예를 들어

 

GCF + ACDEB 의 경우

 

ACDEB라는 단어는  5글자로 A,C,D,E,B에 각각 9,8,7,6,5 를 대입해주면

98765 라는 숫자가 나온다.

 

즉 A에는 9를 넣고 B에는 5를 넣었는데 결론적으로

A = 90000 B = 5가 된 셈이다.

즉 단어의 길이가 길면서 앞쪽에 있는 알파벳들이 가지는 영향력이 크다는 의미이다.

 

따라서 ACDEB라는 단어가 주어졌을때 각각의 알파벳이 0~9중에 어떤 숫자를 배정받게 될지는 모르지만 확실한것은 

각각 배정받은 숫자에서

A는 10000배의

C는 1000배의

D는 100배의

E는 10배의

B는 그 숫자만큼의 영향력(전체 합의 수치를 바꿔주는)을 가지게 된다.

 

---

알고리즘 전략

따라서 단어들이 주어졌을 때 각각의 알파벳들이 가지는 영향력의 크기들을 모두 더해서 배열에 저장해놓은뒤 그 영향력이 가장 큰 순서대로 9,8,7,6... 을 배정해주고 그 최종 합을 구해주면 그 답이 수의 합을 최대로 만드는 숫자가 될것이다.

 

 

n = int(input(""))
arr = []

answer = []
for i in range(0,100):
    answer.append(0)

for i in range(0,n):
    x = input("")
    arr.append(x)

# 단어의 위치에 따라 각각의 알파벳들의 영향력들을 누적해서 배열에 저장해준다
for i in range(0,n):
    for j in range(0,len(arr[i])):
        answer[ord(arr[i][j])] = answer[ord(arr[i][j])] + pow(10,len(arr[i]) -j -1)

ans = []
for i in range(0,100):
    if(answer[i] != 0):
        ans.append(answer[i])

# 최종적으로 등장했던 알파벳들의 영향력을 큰 순서대로 정렬해서 9,8,7.. 순서대로 곱한값들의 합을 출력한다
ans.sort(reverse=True)
count = 9
final = 0
for i in range(0,len(ans)):
    final = final + ans[i]*count
    count = count - 1
print(final)

 

사실 이 문제에서는 N개의 단어들의 수의 합을 최대로 만드는 프로그램을 만드는것이기 때문에 최종적으로 최대합값만 출력하면된다.

따라서 어떤 알파벳에 어떤 숫자를 배정했는지는 궁금하지 않다.

따라서 마지막 sort부분부터 각각의 알바펫들이 가진 영향력들만 가지고(각각에 해당하는 알파벳이 무엇인지 모른채로) 최종 답을 도출하게 된다.