글 읽기 - 시간초과가 나는데...

gktgnjftm 5년 전 0

백트래킹으로 시간초과를 줄일수 있는방법이 있을까요? 제 머리는 저기까지인거같은데 별다른 묘수가 안떠오르네요 끙끙

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
char alpha[10];
int arr[10];
bool visited[10];
char word[11][9];
int leng[10];
int n,Max,sum;
void go(int index) {
	if (index == 10){
		int sum = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; word[i][j]!='\0'; j++) {
				char c = word[i][j];
				sum += arr[c - 65] * pow(10, leng[i]- j - 1);
			}
		}
		Max=max(sum, Max);
		return;
	}
	for (int i = 0; i < 10; i++){
		if (!visited[i]) {
			visited[i] = true;
			alpha[index] = i + 65;
			arr[index] = i;
			go(index + 1);
			visited[i] = false;
			alpha[index] =0;
			arr[index] = 0;
		}
	}
}
int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", word[i]);
		leng[i]=strlen(word[i]);
	}
	go(0);
	printf("%d\n", Max);
	return 0;
}

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

문제

문제

출처

ICPC

시간초과가 나는데...

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말