글 읽기 - 놓치고 있는게 있을까요? 시간초과는 나지않습니다

alsgud3229 5년 전 0

BT함수(백트래킹)의 if 부분에서 모두 출력해주면서 순열이 생성되는 것을 확인하고 이를 토대로 값을 계산해주었습니다.

시간초과는 나지않고 바로 틀렸습니다가 나오는데 어느부분을 놓치고 있는 걸까요?

다른 질문글에 첫숫자가 0이 되지 않도록 해야할수도 있다해서 그렇게도 해보았는데 여전히 틀렸습니다가 나옵니다.

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

using namespace std;

int n;
char word[12][10]; 
char alpha[10] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };
int contain[10];
int num[10] = { 0,1,2,3,4,5,6,7,8,9 };
bool visited[10];
int maxx = -789;

int calculate() {
	int temp = 0;
	int power = 1;
	int len = 0;
	for (int i = 0; i < n; i++) {
		len = strlen(word[i]);
		power = 1;
		for (int j = len-1; j >=0 ; j--) {
			if (word[i][j] == 'A') {
				temp += contain[0] * power;
			}
			else if (word[i][j] == 'B') {
				temp += contain[1] * power;
			}
			else if (word[i][j] == 'C') {
				temp += contain[2] * power;
			}
			else if (word[i][j] == 'D') {
				temp += contain[3] * power;
			}
			else if (word[i][j] == 'E') {
				temp += contain[4] * power;
			}
			else if (word[i][j] == 'F') {
				temp += contain[5] * power;
			}
			else if (word[i][j] == 'G') {
				temp += contain[6] * power;
			}
			else if (word[i][j] == 'H') {
				temp += contain[7] * power;
			}
			else if (word[i][j] == 'I') {
				temp += contain[8] * power;
			}
			else if (word[i][j] == 'J') {
				temp += contain[9] * power;
			}
			power = power * 10;
		}
	}
	return temp;
}

void BT(int walker) {
	if (walker >= 10) {
		// container와 alpha로 각 문자의 값 조합
		int temp = 0;
		temp = calculate();
		if (maxx < temp) {
			maxx = temp;
		}
		return;
	}

	for (int i = 0; i < 10; i++) {
		if (!visited[i]) {
			visited[i] = true;
			contain[walker] = num[i];
			BT(walker + 1);
			contain[walker] = 0;
			visited[i] = false;
		}
	}
}

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

	BT(0);

	cout << maxx << "\n";

	return 0;
}

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

문제

문제

출처

ICPC

놓치고 있는게 있을까요? 시간초과는 나지않습니다

alsgud3229 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말