[C++] 백준 1339번 풀이 (단어 수학)

- 문제 (1339번) : 단어 수학

• 링크 : https://www.acmicpc.net/problem/1339

• 알파벳 대문자를 입력받았을 때 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔 그 수들을 합할 때 제일 큰 값으로 만드는 문제

---

- 입력 및 출력

[입력]

• 첫째 줄에 단어의 개수 N 입력
• 둘째줄부터 N개의 줄에 단어를 한줄에 하나씩 입력

※ 각 입력값들의 제한범위

• 단어의 개수 (N) : 1 ≤ N ≤ 10
• 단어 당 알파벳 개수 (M) : 1 ≤ M ≤ 10
• 수의 최대 길이 : 8

[출력]

• 주어진 단어의 합의 최댓값 출력

---

- 문제 풀이

1. 입력받은 단어를 하나의 수로 생각해 해결한다.

   • ex) ABC 이면 100A + 10B + 1C 로 생각

2. 여러개의 단어를 입력받은 경우 위와 같은 방법으로 생각한다.

   • ex) ABC, ABCD 입력받은 경우
     ABC -> 100A + 10B + 1C
     ABCD -> 1000A + 100B + 10C + 1D
     ∴ 1100A + 110B + 11C + 1D 로 생각하면 됨.

3. 위와같이 계산해 도출해낸 방정식의 계수들을 기준으로 큰 수 -> 작은 수로 내림차순 정렬을 한다.

   • ex) ABC 인 경우 -> 100A + 10B + 1C
     alpha[A] = 100
     alpha[B] = 10
     alpha[C] = 1

     • 이 때 배열 index의 A, B, C는 'A'의 아스키코드값을 뺀 index 값임.
     • ex) alpha[A] == alpha[ A - 'A' ] == alpha[0]
       ex) alpha[B] == alpha[ B - 'A' ] == alpha[1]
       ex) alpha[C] == alpha[ C - 'A' ] == alpha[2]

4. 3.의 과정에서 정렬한 값을 바탕으로 계수가 가장 큰 문자부터 순서대로 9, 8, 7 ... 1까지 곱해 더해주면 가장 큰 합이 될 수 있다.

   • ex) 3.에서 내림차순으로 정렬했을 때 (100A + 10B + 1C )
     alpha[0] = 100 x 9
     alpha[1] = 10 x 8
     alpha[2] = 1 x 7
     ∴ 900 + 80 + 7 = 987

---

- 최종 코드

---

- 참고 링크

• 블로그 : https://excited-hyun.tistory.com/145