백준 #1132 합

이번 문제는 Gold I 난이도입니다.  난이도상으로는 꽤 어려운 문제입니다. 복면산 풀 듯이 풀면 됩니다.

 

 

verbal arithmetic

 

그렇지만, 사실 어려운 문제는 아닙니다.  복잡한 알고리즘이 들어가는 것도 아니고, 구현이 복잡한 것도 아닙니다.

 

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

1132번: 합

문제는 A~J 로 이루어진 문자열에 숫자를 대입해서 그 숫자들의 합이 최대가 되도록 할 때, 그 합을 출력하는 것입니다.

예를 들어서 ABC, BAC, CAB 가 있다고 해보죠. A = 9, B = 8, C = 7 이라고 하면, 987+897+798=2,682 가 되겠죠.  그런데 A=7, B=8, C=9 라고 한다면, 789+879+978=2,646 이 됩니다.  구성되는 숫자가 똑같아도 그 결과는 달라집니다.  AAA, ABB, BBA 와 같이 하나의 문자열에 여러번 문자가 나타나도 상관이 없습니다.

 

이 문제는 탐욕 알고리즘으로 풀 수 있습니다.  탐욕 알고리즘으로 푼다면, Gold I 난이도는 정말 무색합니다.  이보다 어려운 Silver 문제들이 널려있으니까요.

 

문자가 나올때마다, 각 자릿수에 맞는 값을 더해간 다음 정렬하면 이 문제를 쉽게 풀 수 있습니다.

 

예제로 돌릴 수 있는 경우들을 나열합니다.

3
ABCDEFGHIJ
BCDEFABCABB
EFGHIJABCDEF
==> 1066472147195

9
A
BBBBBB
CCCCCC
DDDDDD
EEEEEE
FFFFFF
GGGGGG
HHHHHH
IJJJJJJ
==> 12888886

8
A
BB
CCC
DDDD
EEEEE
FFFGGG
HHHHHHH
IJJJJJJJ
==> 107393020