글 읽기 - 시간 초과인 이유를 잘 모르겠습니다.

jlee4923 3년 전 0

IDE에서 시간이 좀 오래 걸리기는 해도 출력은 다 잘 됩니다.

재귀 호출을 하는 부분에서 불필요한 부분이 있는것 같은데, 어떻게 수정해야 할 지 한참 생각해도 잘 모르겠습니다.

도와주십쇼..

#include <stdio.h>
#include <stdlib.h>
const int a = 2190;
const int b = 2190;
void draw(int n, char d[a][b], int s_row, int s_col)
{
	if(n==3){
		for(int i= s_row; i<s_row+n; i++){
			for(int j= s_col; j<s_col+n; j++){
				if(i!=s_row+1 || j!=s_col+1){
					d[i][j]= '*';
				}
			}
		}
		return;
	}
	for(int i=0; i<9; i++){
		for(int j=s_row; j<n+s_row; j+=(n/3)){
			for(int k=s_col; k<n+s_col; k+=(n/3)){
				if(j!=s_row+(n/3) || k!=s_col+(n/3)){ 
						draw(n/3, d, j, k);
				}
			}
		}
	}
}
int main()
{
	int n;
	char d[2190][2190];
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			d[i][j]=' ';
		}
	}
	draw(n,d,0,0);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			printf("%c",d[i][j]);
		}
		printf("\n");
	}
	return 0;
}

ghkdiwl 3년 전 1

for(int i=0;i<9;i++) 부분은 필요없어 보여요 !

jlee4923 3년 전 0

for(int i=0;i<9;i++) 이 부분이 시간 초과라는 결과에 큰 영향을 주나요? 9가 상수라서 시간복잡도에는 큰 영향을 미칠거 같지 않다고 생각했습니다.

물론 수정한 후 맞긴 했습니다.. 답변 주시면 감사하겠습니다.

ghkdiwl 3년 전 0

재귀에서는 반복문에 따라 진입횟수가 기하급수적으로 늘어납니다.

예를들어 첫번째 레벨에서 반복문으로 2번 진입하는 경우 반복문을 사용하지 않는 경우와 비교했을 때 2배의 작업량이 생기겠죠.

그리고 반복문을 사용하는 경우 두번째 레벨에서 다시 2번 진입하니 두번째 레벨까지만 봐도 2*2= 4배의 작업량이 발생합니다.

그리고 들어가면 들어갈수록 계속해서 8,16,32 .. 배의 작업량이 생기겠죠.

최종적으로는 반복문을 사용하지 않았을 경우와 비교해서 엄청난 양의 차이가 발생합니다.

밑에 소스 보시면 반복문으로 두 번 진입하는 경우 5번째 레벨까지 진입했을 때 32배의 차이가 나는것을 확인하실 수 있어요.

#include<iostream>
using namespace std;
int btrc1(int cnt) {
	if (cnt == 0) return 1;
	int temp = 0;
	temp += btrc1(cnt - 1);
	return temp;
}
int btrc2(int cnt) {
	if (cnt == 0) return 1;
	int temp = 0;
	for (int i = 0; i < 2; i++) temp += btrc2(cnt - 1);
	return temp;
}
int main() {
	cout << btrc1(5) << '\n';
	cout << btrc2(5) << '\n';
}

jlee4923 3년 전 0

좋은 답변 감사합니다. 이해되었습니다.

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

문제

문제

출처

ICPC

시간 초과인 이유를 잘 모르겠습니다.

jlee4923 3년 전 0

ghkdiwl 3년 전 1

jlee4923 3년 전 0

ghkdiwl 3년 전 0

jlee4923 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말