글 읽기 - 시간초과가 발생하는 이유 요리보고 조리봐도 모르겠습니다

dsa2341 4년 전 0

쉬울 줄 알고 도전해봤는데 시간초과가 왜 발생하는지 모르겠습니다. 시간을 어떻게 줄여야할까요.

check 함수가 문제인가 싶어서 인덱스를 미리 다 저장해두고 비교해봐도 시간초과였습니다

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int n;
char al[12], star[5][9];
vector<pair<int, int>> v;
bool check() {
	int tmp[6] = { 0 };
	for (int j = 1; j < 8; j += 2) {
		tmp[0] += (star[1][j] - 'A' + 1);
		tmp[1] += (star[3][j] - 'A' + 1);
	}
	for (int i = 0, j = 4, k = 0; k < 4; ++i, ++k) {
		tmp[2] += (star[i][j - k] - 'A' + 1);
		tmp[3] += (star[i][j + k] - 'A' + 1);
	}
	for (int i = 4, j = 4, k = 0; k < 4; --i, ++k) {
		tmp[4] += (star[i][j - k] - 'A' + 1);
		tmp[5] += (star[i][j + k] - 'A' + 1);
	}
	for (int i = 0; i < 6; ++i)
		if (tmp[i] != 26) return false;
	return true;
}
void solve(int cur) {
	if (cur == n) {
		if (check()) {
			for (int i = 0; i < 5; ++i) {
				for (int j = 0; j < 9; ++j)
					cout << star[i][j];
				cout << "\n";
			}
			exit(0);
		}
		return;
	}
	int nowy = v[cur].first, nowx = v[cur].second;
	for (int i = 0; i < 12; ++i) {
		if (al[i]) continue;
		al[i] = 1, star[nowy][nowx] = i + 'A';
		solve(cur + 1);
		al[i] = 0, star[nowy][nowx] = 'x';
	}
}
int main()
{
	for (int i = 0; i < 5; ++i)
		for (int j = 0; j < 9; ++j) {
			cin >> star[i][j];
			if (star[i][j] >= 'A' && star[i][j] < 'L')
				al[star[i][j] - 'A'] = 1;
			else if (star[i][j] == 'x')
				v.push_back({ i,j });
		}
	n = v.size();
	solve(0);
	return 0;
}

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

문제

문제

출처

ICPC

시간초과가 발생하는 이유 요리보고 조리봐도 모르겠습니다

dsa2341 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말