[백준 1339] 단어 수학 (C#, C++) - soo:bak

문제 링크

1339번 - 단어 수학

설명

N개의 단어가 주어지는 상황에서, N (1 ≤ N ≤ 10)과 각 단어(알파벳 대문자로만 구성, 길이 ≤ 8)가 주어질 때, 각 알파벳을 0부터 9까지의 서로 다른 숫자로 바꾸어 만든 수들의 합이 최대가 되도록 하는 문제입니다.

같은 알파벳은 같은 숫자로, 다른 알파벳은 다른 숫자로 대응되어야 하며, 단어에 등장하는 서로 다른 알파벳은 최대 10개입니다.

접근법

합을 최대로 만들려면 가장 영향력이 큰 알파벳에 가장 큰 숫자를 할당해야 합니다.

각 알파벳의 영향력은 그 알파벳이 등장하는 모든 자리수의 자리값을 합한 것입니다.

예를 들어, “ABC”라는 단어가 있다면:

• A는 백의 자리에 있으므로 영향력 = 100
• B는 십의 자리에 있으므로 영향력 = 10
• C는 일의 자리에 있으므로 영향력 = 1

만약 A=9, B=8, C=7로 할당하면 ABC = 987이 됩니다.

여러 단어가 있는 경우, 같은 알파벳이 여러 번 등장할 수 있습니다.

예를 들어, “AAA”와 “AAA” 두 단어가 있다면:

• A는 첫 번째 단어에서: 100 + 10 + 1 = 111
• A는 두 번째 단어에서도: 100 + 10 + 1 = 111
• A의 총 영향력 = 222

A=9로 할당하면 AAA = 999이고, 두 단어의 합 = 999 + 999 = 1998 = 222 × 9가 됩니다.

다른 예로, “GCF”와 “ACDEB”가 주어진 경우:

• G: 100 (GCF의 백의 자리)
• C: 10 (GCF의 십의 자리) + 10000 (ACDEB의 만의 자리) = 10010
• F: 1 (GCF의 일의 자리)
• A: 10000 (ACDEB의 십만의 자리)
• D: 1000 (ACDEB의 천의 자리)
• E: 100 (ACDEB의 백의 자리)
• B: 1 (ACDEB의 일의 자리)

영향력 순서: C(10010) > A(10000) > D(1000) > E(100) > G(100) > F(1) > B(1)

C=9, A=8, D=7, E=6, G=5, F=4, B=3으로 할당하면:

• GCF = 954
• ACDEB = 87763
• 합 = 88717

모든 알파벳의 영향력을 계산한 후, 영향력이 큰 순서대로 9, 8, 7, …을 할당하여 최대 합을 구합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var words = new string[n];
      for (var i = 0; i < n; i++)
        words[i] = Console.ReadLine()!;

      var weight = new long[26];
      foreach (var word in words) {
        var placeValue = 1L;
        for (var i = word.Length - 1; i >= 0; i--) {
          var index = word[i] - 'A';
          weight[index] += placeValue;
          placeValue *= 10;
        }
      }

      Array.Sort(weight, (a, b) => b.CompareTo(a));

      var sum = 0L;
      var digit = 9;
      for (var i = 0; i < 26 && weight[i] > 0; i++) {
        sum += weight[i] * digit;
        digit--;
      }

      Console.WriteLine(sum);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<string> vs;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vs words(n);
  for (int i = 0; i < n; i++)
    cin >> words[i];

  vll weight(26, 0);
  for (const auto& word : words) {
    ll placeValue = 1;
    for (int i = (int)word.size() - 1; i >= 0; i--) {
      weight[word[i] - 'A'] += placeValue;
      placeValue *= 10;
    }
  }

  sort(weight.begin(), weight.end(), greater<ll>());

  ll sum = 0;
  int digit = 9;
  for (int i = 0; i < 26 && weight[i] > 0; i++) {
    sum += weight[i] * digit;
    digit--;
  }

  cout << sum << "\n";
  
  return 0;
}