글 읽기 - 어느 부분이 시간초과를 야기하는 것일까요?? 도와주세요!!

mhccc 5년 전 0

코드에서 어떤 부분이 시간적으로 비효율적인 것인지 알아내기가 어렵습니다 ㅜㅜ.

보아하니 O(1)로 푸는 방법도 있는 것 같지만 각 칸마다 직선과 대각선을 검사하는 방식으로도

풀 수는 있는 것 같은데 제 코드는 시간초과가 나오네요. 도와주세요!!

#include <iostream>
using namespace std;
bool check[15][15];
int go(int r, int n) {
	int sum = 0; 
	if(r == n) {
		return 1;
	}
	for(int c=0; c<n; c++) {
		check[r][c] = true;
		bool flag = true;
		for(int i=r-1; i>=0; i--) {
			if(check[i][c] || (check[i][c-(r-i)] && 0<=c-(r-i)) || (check[i][c+(r-i)] && c+(r-i)<n)) {
				flag = false;
			}
		}
		if(flag) {
			sum += go(r+1, n);
		}
		check[r][c] = false;
	}
	return sum;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	cout << go(0, n);
	return 0;
}

sgchoi5 5년 전 2

여기 소개하는 책의 85 페이지에 해당 문제에 대한 정석풀이가 있습니다.

그 내용을 보시는게 좋을 것 같습니다.

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

문제

문제

출처

ICPC

어느 부분이 시간초과를 야기하는 것일까요?? 도와주세요!!

mhccc 5년 전 0

sgchoi5 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말