#1339 단어 수학(Mathematics)

이번 문제는 복면산과 비슷한 개념의 문제입니다.  A~Z까지의 문자가 사용되며, 각각의 문자는 서로 다르면서 0~9까지의 숫자 중 하나가 사용될 수 있습니다.  복면산 문제들은 퍼즐 형태로도 나와서 아마 풀어본 분들이 많을겁니다.

 

대표적인 복면산 문제들이 몇가지가 있죠.

 

예를 들어서 아래 그림과 같이 "Send More Money"라는 문구를 가지고 만든 복면산은 널리 알려져 있습니다.

 

Word Math

이번문제는 A~Z로 이루어진 여러개의 단어의 합을 최대로 하기 위해서 적절한 숫자를 대입해서 그 합을 출력하는 것입니다.  문제 자체는 아주 쉽고, 사실 풀이도 어렵지 않지만, 난이도 Gold IV 문제입니다.

 

제가 푼 방식은 단어가 나올 때마다, 각 자릿수의 문자를 기록하고, 그 합을 계산했습니다.  예를 들어서 ABC, BCD 두 단어가 있다면, 각 문자의 자릿수와 빈도를 기록합니다.  빈도를 기록한 테이블은 아래와 같습니다.

 

Character	100	10	1	Total
A	1			100
B	1	1		110
C		1	1	11
D			1	1

 

각각의 빈도에 따라서 합을 구하면 B > A > C > D 형태의 순서가 됩니다.  그러면 가중치가 가장 큰 수에 9를 가장 작은 가중치의 숫자에 0을 대입하면 됩니다.  위의 경우에는 B=9, A=8, C=7, D=6 이 되고, 가중치를 곱한 결과는 \(990+800+77+6 = 1873\)이 됩니다.  실제로 \(897+976 = 1873\)이 됨을 알 수 있습니다.

 

이 알고리즘을 바탕으로 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1339 - Word Matematics
//    - by Aubrey Choi
//    - created at 2019-07-04
//--------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <algorithm>

int main()
{
  int n, len, v, param[26] = {0, }, i; char str[10];
  scanf("%d", &n);
  while(n--)
  {
    scanf("%s", str);
    len = strlen(str);
    for(i=1,v=1;i<len;i++,v*=10);
    for(i=0;i<len;i++,v/=10) param[str[i]-'A'] += v;
  }
  std::sort(param, param + 26);
  int sum = 0;
  for(i = 0; i < 10; i++) sum += param[i+16] * i;
  printf("%d\n", sum);
}