글 읽기 - 백트래킹 풀이 시간초과가 납니다..

bbwwpark 4년 전 0

0~9 숫자 10개에서 알파벳의 개수 만큼 순열을 뽑고, 뽑을때마다 단어 숫자 변환을 하여 계산을 해주고 최대값을 찾는 방식으로 구현했습니다. 그런데 시간이 너무 오래걸리네요

알파벳이 10개 일때 10개에서 10개를 뽑은 순열이여서 시간이 너무 오래 걸립니다..

백트래킹 방법으로 풀고싶은데, 어떻게 하면 될까요? 제 접근 방법이 에초에 잘못된걸까요?

//1.N개에서 N개를 뽑는 순열을 구한다.
//2.순열을 구할때마다 계산함.

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;


int n;//단어 개수
int m; // m개를 뽑는다. (순열)
char words[10][8];
int ret_max = 0x7fffffff * -1;
bool visited[10];
vector<int> v;

int calcul() {
	int res = 0;
	for (int i = 0; i < n; i++) {
		int sum=0;
		for (int j = 0; j < strlen(words[i]); j++) {
			int idx = words[i][j] - 'A';
			if (sum == 0) {
				sum += v[idx];
			}
			else {
				sum *= 10;
				sum += v[idx];
			}
		}
		res += sum;
	}
	return res;
}

void dfs() {//10개에서 m개 뽑기 
	if (v.size() == m) { //m개를 뽑는다면, 계산
		//단어 숫자 합 계산
		/*
		for (int i : v) {
			printf("%d ", i);
		}
		puts("");*/
		int ret = calcul();
		if (ret > ret_max)
			ret_max = ret;
		return;
	}
	
	for (int i = 9; i>=10-m; i--) {
		if (!visited[i]) {
			visited[i] = true;
			v.push_back(i);
			dfs();
			v.pop_back();
			visited[i] = false;
		}
	}
}

int main() {
	char maxCh = 'A'; //가장 큰 단어
	cin >> n;
	for (int i = 0; i < n; i++) { //입력
		scanf("%s", words[i]);
		getchar();
	}

	for (int i = 0; i < n; i++) { //가장큰 문자 찾기
		for (int j = 0; j < strlen(words[i]); j++) {
			if (words[i][j] > maxCh)
				maxCh = words[i][j];
		}
	}

	//printf("%c\n", maxCh);

	for (int i = 0; i < 10; i++) {//문자 개수 찾기
		if (maxCh == 'A' + i)
			m = i + 1;
	}

	//printf("%d\n", m);

	dfs(); //  순열 구하기

	printf("%d", ret_max);
}

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

문제

문제

출처

ICPC

백트래킹 풀이 시간초과가 납니다..

bbwwpark 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말