[백준 1339] 단어 수학

www.acmicpc.net/problem/1339

1339번: 단어 수학

백트래킹 문제여서 백트래킹으로 풀었더니 답은 맞았지만 엄청나게 시간이 오래 걸렸다.

엄청난 시간 차이....

아래 제출한 기록이 백트래킹으로 풀었을 때 걸리는 시간이다.

백트래킹 로직은

1. 사용된 모든 알파벳을 담은 후

2. 각 알파벳에 숫자를 매칭시켜서 (백트래킹)

3. 최댓값을 구한 것이다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> v(11);

int alpha[26];
bool visited[10];
char c[10];
int n, res = -1, wordNum = 0;

int findIdx(char str)
{
  for (int i = 0; i < wordNum; i++)
  {
    if (c[i] == str)
    {
      return i;
    }
  }
}

void BackTracking(int cnt, vector<int> &order)
{
  if (cnt == wordNum)
  {
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
      int tmp = 0;
      for (int j = 0; j < v[i].length(); j++)
      {
        tmp *= 10;
        tmp += order[findIdx(v[i][j])];
      }
      sum += tmp;
    }
    res = max(sum, res);
    return;
  }

  for (int i = 0; i <= 9; i++)
  {
    if (visited[i])
      continue;
    order[cnt] = i;
    visited[i] = true;
    BackTracking(cnt + 1, order);
    visited[i] = false;
  }
}
int main(void)
{

  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n;

  for (int i = 0; i < n; i++)
  {
    cin >> v[i];
    for (int j = 0; j < v[i].length(); j++)
    {
      alpha[v[i][j] - 'A'] = 1;
    }
  }

  for (int i = 0; i < 26; i++)
  {
    if (alpha[i] == 1)
    {
      c[wordNum++] = i + 'A';
    }
  }
  vector<int> order(wordNum);

  BackTracking(0, order);
  cout << res << "\n";

  return 0;
}

 

 

하지만...다른 사람들을 보니 0ms 소요되는 문제였다... 사실 알파벳은 중요하지 않았다. 

한 알파벳이 어떤 자리에 등장했는지가 더 중요했다.

 

다른 사람들의 로직은 

1. 인풋을 받으면서 alpha 배열에 1의 자리, 10의 자리, 100의 자리 이런 식으로 자리 수를 매칭시킨다.

2. 소팅한다.

3. 큰 수부터 9에 매칭시킨다.

 

이렇게 하면 자연스럽게 최댓값이 나온다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int alpha[26];
int n;
string tmp;
int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> tmp;
    //idx는 자리값
    for (int idx = 1, j = tmp.length() - 1; j > -1; j--, idx *= 10)
    {
      alpha[tmp[j] - 'A'] += idx;
    }
  }
  sort(alpha, alpha + 26);

  int res = 0;
  for (int idx = 9, i = 25; alpha[i]; i--, idx--)
  {
    res += alpha[i] * idx;
  }

  cout << res << "\n";

  return 0;
}