글 읽기 - 연산자의 갯수에 따라 전체 시간복잡도가 변할 수도 있나요?

disdong123 3년 전 0

우선 출력은 제대로 나오는데, 시간초과가 발생합니다

promising 내부에 n=15인 for문 하나가 존재하는데 이 for문의 로직만 바꾸면 ac가 됩니다.

for문 내부의 if문의 갯수나 연산자의 갯수가 전체 시간복잡도에서 유의미한 차이를 낼 수 있는건가요??

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <climits>
using namespace std;

int n, res;
bool a[15][15];

bool promising(int row, int col) {
	for (int i = 0; i < n; i++) {

		if (a[row][i]) return false;
		if (a[i][col]) return false;
		if (row + i < n && col + i < n && a[row + i][col + i]) return false;
		if (row - i >= 0 && col - i >= 0 && a[row - i][col - i]) return false;
		if (row - i >= 0 && col + i < n && a[row - i][col + i]) return false;
		if (row + i < n && col - i >= 0 && a[row + i][col - i]) return false;
	}
	return true;
}


void dfs(int cnt) {
	if (cnt == n) {
		res++;
		//for (int i = 0; i < n; i++) {
		//	for (int j = 0; j < n; j++) {
		//		if (a[i][j]) cout << 1<< " ";
		//		else cout << 0 << " ";
		//	}
		//	cout << endl;
		//}
		//cout << endl;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (a[cnt][i] || !promising(cnt, i)) continue;
		a[cnt][i] = true;
		dfs(cnt + 1);
		a[cnt][i] = false;
	}
}
int main() {
	cin >> n;
	dfs(0);
	cout << res << endl;
}

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

문제

문제

출처

ICPC

연산자의 갯수에 따라 전체 시간복잡도가 변할 수도 있나요?

disdong123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말