글 읽기 - 시간초과라고 뜨는데 어떤식으로 개선을 하면 좋을까요...

byssiw 6년 전 0

답은 제대로 구하는거 같은데 시간 초과네요...

이것저것 시도는 해보았는데 실패해서...어떻게 시간을 줄일 수 있을지 좋은 방법 있으면 부탁드립니다! ㅠㅠ

#include <stdio.h>
#include <string.h>

int M, N, day = 0, chk = 0;
int tomato[1000][1000], temp[1000][1000];

int chk_tomato();
void ripe_tomato();

int main(void){

	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			scanf("%d", &tomato[i][j]);
		}
	}

	ripe_tomato();
	printf("%d\n", day);
	
	return 0;
}

void ripe_tomato(){

	memcpy(temp, tomato, sizeof(int) * 1000 * 1000);
	if (chk_tomato() == 1) return; //이미 다 익었는지 확인
	
	do{
		chk = 0;
		for (int i = 0; i < N; i++){
			for (int j = 0; j < M; j++){
				if (tomato[i][j] == 1){              
					if (j - 1 >= 0 && tomato[i][j - 1] == 0) {
						temp[i][j - 1] = 1; //좌측 익히기
						chk = 1;
					}
					if (j + 1 < M && tomato[i][j + 1] == 0) {
						temp[i][j + 1] = 1; //우측 익히기
						chk = 1;
					}
					if (i - 1 >= 0 && tomato[i - 1][j] == 0){
						temp[i - 1][j] = 1; //위쪽 익히기
						chk = 1;
					}
					if (i + 1 < N && tomato[i + 1][j] == 0){
						temp[i + 1][j] = 1; //아래쪽 익히기
						chk = 1;
					}
				}
			}
		}
		day++;
		memcpy(tomato, temp, sizeof(int) * 1000 * 1000);
	} while (chk_tomato() == -1 && chk == 1);

	if (chk_tomato() != 1) day = -1;
}

int chk_tomato(){

	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			if (temp[i][j] == 0) return -1; //안익은 토마토 있으면 -1 반환
		}
	}

	return 1; //다 익었으면 1반환
}

upple1 6년 전 0

mempy가 일일히 복사하는 것일텐데 while문이 100번만 반복되도 연산이 억번 대 이상하는거라 시간초과가 발생하는 것 같네요.

다른 방법 알아보셔야 할 것 같네요

https://ko.wikipedia.org/wiki/...

이 링크가서 한번 공부하시면 도움되실 것 같습니다.

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

문제

문제

출처

ICPC

시간초과라고 뜨는데 어떤식으로 개선을 하면 좋을까요...

byssiw 6년 전 0

upple1 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말