합의 최댓값

면접 대비

시간 제한2초메모리 제한128 MB

요약
N개의 숫자를 알파벳 A부터 J까지의 문자로 암호화했을 때, 각 문자에 0부터 9까지의 숫자를 배정해 선행 0이 없도록 하면서 전체 합을 최대화합니다.
난이도

보통10점 중 5점

유형
그리디, 수학, 정렬, 문자열
정답자
아직 제출이 없습니다

문제

N개의 수가 주어진다. 모든 수는 자연수이지만, 각 자리는 숫자 대신 알파벳 A부터 J까지의 문자로 적혀 있다. 각 문자는 정확히 하나의 숫자를 뜻하고, 각 숫자도 정확히 하나의 문자에 대응한다. 어떤 수도 0으로 시작하지 않는다. 가능한 N개 수의 합 중 최댓값을 구하자.

입력

첫째 줄에 자연수 N이 주어진다. N은 50 이하이다. 둘째 줄부터 N개의 줄에는 각 수가 하나씩 주어진다. 각 수의 길이는 최대 12이다. 적어도 하나의 알파벳은 어떤 수의 첫 문자로도 등장하지 않는다.

출력

합의 최댓값을 출력한다.

예제5

  1. 예제 1

    입력
    2
ABC
BCA
    예상 출력
    1875

  2. 예제 2

    입력
    1
ABCDEFGHIJ
    예상 출력
    9876543210

  3. 예제 3

    입력
    2
ABCDEFGHIJ
J
    예상 출력
    9876543202

  4. 예제 4

    입력
    10
A
BB
CCC
DDDD
EEEEE
FFFFFF
GGGGGGG
HHHHHHHH
IIIIIIIII
AJJJJJJJJJ
    예상 출력
    9973936905

  5. 예제 5

    입력
    5
GHJIDDD
AHHCCCA
IIJCEJ
F
HDBIGFJAAJ
    예상 출력
    9888114550