글 읽기 - 단어수학 질문드립니다(시간초과-백트랙킹)

kysu5095 3년 전 0

map 자료구조를 사용하여 입력된 문자열의 문자를 map에 저장하였습니다.

후에 dfs함수를 돌면서 map에 들어있는 문자들에 점수를 부여해 준 후

dfs의 마지막 단계에서 결과값을 계산해주는 알고리즘을 사용하였습니다.

제출하면 1%에서 바로 시간초과가 나는데 어느부분에서 나는지 모르겠습니다ㅠ

틀린부분 지적해주시면 감사하겠습니다.

// 단어 수학

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <map>

using namespace std;

int n, res = 0;
vector<string> v;
map<char, int> m;

// 부여된 점수를 더함
void cal() {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int tmp_sum = 0;
		int len = v[i].length();
		for (int j = 0; j < len; j++) 
			tmp_sum += ((m.find(v[i][j])->second) * pow(10, len - 1 - j));
		sum += tmp_sum;
	}
	res = max(res, sum);
}

// backtracking
void dfs(int cnt) {
	if (cnt == 10) {
		cal();
		return;
	}
	map<char, int>::iterator iter;
	// 각 단어마다 점수 부여
	for (iter = m.begin(); iter != m.end(); iter++) {
		if (iter->second == -1) {
			iter->second = cnt;
			dfs(cnt + 1);
			iter->second = -1;
		}
	}
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int cnt = 0;
	cin >> n;
	for(int i = 0; i < n; i++) {
		string str;
		cin >> str;
		v.push_back(str);
		// 문자열에서 단어를 뽑아 저장
		for (int j = 0; j < str.length(); j++) 
			m[str[j]] = -1;
	}
	cnt = m.size();
	dfs(10 - cnt);
	cout << res << '\n';
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

단어수학 질문드립니다(시간초과-백트랙킹)

kysu5095 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말