BaekJoon 1339 단어 수학

Link https://www.acmicpc.net/problem/1339

소스결과 1988 KB / 1716 ms

출처 Baekjoon

언어 C++ 17

분류 수학 백트래킹

 

설명

단어로 된 수학 문제를 푸는 숙제를 받은 민식이를 도와주자.

각 알파벳에 대해서 0 ~ 9 사이의 숫자를 대입했을 때 합이 최대는 값을 찾아주자

 

백트래킹으로 풀기에는 생각보다 간당간당한 문제

처음에는 사용되는 알파벳에 9부터 역순으로 값을 대입해 보는 방법을 사용했지만 결과는 시간초과

TC조차도 상당히 오랜 시간이 걸렸다.

두번째로 선택한 방법은 사용되는 알파벳이 최대 10개이기에 10개에 맞춰 저장을 하고 각 값에 대해서 값을 지정하고

모든 값이 지정이 된다면 값을 치환해 결과를 구하는 방식으로 구했다.

두번째 방법이 되려 첫번째 방법보다 연산이 많아 시간이 오래 걸릴 것 처럼 보였지만 되려 시간이 단축되었다.

 

알고리즘

1. n개의 문자를 vector에 저장한다.

2. 각 문자를 받을 때 마다 각 문자가 이미 입력이 된 문자인지 확인하고 입력이 되지 않은 문자라면 저장한다.

3. BackTracking을 진행 하면서 각 문자에 9 ~ 0 까지 대입해 결과값을 계산하고 최대값보다 크다면 최대값을 갱신한다.

4. 출력

 

소스코드

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 10;
int alphaCount;
int n;
int mxm;

vector<char[MAX+1]> words(MAX);
char useAlpha[MAX];
short alphaValue[MAX];
bool check[MAX];

int find(char c)
{
	for (int i = 0; i < alphaCount; i++)
		if (useAlpha[i] == c)
			return i;
	return -1;
}

void backTrack(int pos)
{
	if (pos == alphaCount)
	{
		int sum = 0;
		/*for (int i = 0; i < alphaCount; i++)
			cout << alphaValue[i] << ' ';*/ // For Debug

		for (int i = 0; i < n; i++)
		{
			int cal = 0;
			int len = strlen(words[i]);
			for (int j = 0; j < len; j++)
				cal = (cal * 10) +  alphaValue[find(words[i][j])];
			sum += cal;

			// cout << cal << ' '; // For debug
		}

		// cout << sum << '\n'; // For debug

		if (mxm < sum)
			mxm = sum;
	}
	else
	{
		for (int i = 0; i < alphaCount; i++)
		{
			if (check[i])
				continue;

			alphaValue[pos] = MAX - i - 1;
			check[i] = true;
			backTrack(pos + 1);
			check[i] = false;
		}
	}
}

int main()
{
	cin >> n;

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

		for (int j = 0; words[i][j] != '\0'; j++)
			if (find(words[i][j]) == -1)
				useAlpha[alphaCount++] = words[i][j];
	}

	backTrack(0);

	cout << mxm;
	return 0;
}