[백준 1339][완전탐색][C++] 단어 수학

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

1339번: 단어 수학

알파벳 종류의 최대 개수가 10개라 시간복잡도가 O(n!)인 순열만 구현하면 쉽게 풀 수 있는 문제였습니다. 

 

다만 알파벳에 숫자를 대입해가며 덧셈을 하면 시간이 부족할까봐(해보진 않아서 시간초과가 뜰지 안뜰지는 모르겠습니다) 더 빠르게 계산을 하기 위해 입력부에서부터 처리를 해줬습니다.

먼저 나온 알파벳의 종류를 벡터에 나온 순서대로 중복없이 담고, 그러면 index마다의 알파벳이 특정되므로 해당 알파벳이 나올 때마다 10^(자릿수-1)만큼 cnt 배열의 알파벳의 ASCII 자리에 더해줬습니다.

만약, 2 AAB BAA 를 입력으로 받는다면 charcnt['A'] 는 121, charcnt['B']는 101이 될 것이므로 A가 1, B가 2를 가진다면 121*1 + 101*2 = 323으로 112+211과 같은 결과를 가집니다.

(→ 112+211 = (110+2)+(200+11) = (110+11)+(200+2) = 121*1 + 101*2)

 

막상 푸니 간단한 문제였는데 처음에 접근을 잘못해서 오래걸린 문제였네요.. 문제 분석 능력을 키워야겠습니다.

 

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

int n, ans;
int charcnt[91];
int numbers[10]={0,1,2,3,4,5,6,7,8,9};
vector<char> existChar;
bool charvisited[91];
string word;

void swap(int &a, int &b){
	int tmp = a; a=b; b=tmp;
}

void solve(int depth){
	if(depth==existChar.size()){
		int val = 0;
		for(int i=0; i<existChar.size(); i++){
			val += charcnt[existChar[i]]*numbers[i];
		}
		ans = max(ans,val);
		return;
	}
	int ans=0;
	for(int i=depth; i<10; i++){
		swap(numbers[depth],numbers[i]);
		solve(depth+1);
		swap(numbers[depth],numbers[i]);
	}
}

int main(){
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>word;
		int wsize = word.length()-1;
		for(char c : word){
			charcnt[c]+=pow(10,wsize--);
			if(charvisited[c]) continue;
			charvisited[c]=true;
			existChar.push_back(c);
		}
	}
	solve(0);
	cout<<ans<<endl;
}