글 읽기 - 시간초과가 나는데 어떤 부분이 시간초과인지 궁금합니다.

baraba6u 4년 전 0

며칠전 전역하고 거의 한 2년만에 처음 프로그래밍 공부를 다시 시작하는 학생입니다.

예전에 공부했던 기억을 더듬고 더듬어 한번 문제를 풀어봤는데

알고리즘 자체는 정확한것 같으나 포도주가 50개만되도 버벅거리면서 오래걸리는것 같습니다.

다른 질문들을 보니 다 저와 비슷한 아이디어를 사용한것 같은데

재귀함수 호출이 문제인가요? 아니면 max함수 호출이 문제인가요?

어떤 부분에서 시간초과가 났으며 해결할려면 어떻게 해야될까요?...

#include <stdio.h>

int max(int a, int b, int c) {
	if (a > b&& a > c) {
		return a;
	}
	if (b > a&& b > c) {
		return b;
	}
	else {
		return c;
	}
}


int MAX = 0, len = 0;
int arr[10000] = { 0 };

int grape(int counter) {
	if (counter + 4 > len) {
		return max(arr[counter] + arr[counter + 1], arr[counter + 1] + arr[counter + 2], arr[counter] + arr[counter + 2]);

	}
	MAX = max(arr[counter] + arr[counter + 1] + grape(counter + 3), arr[counter] + grape(counter + 2), grape(counter + 1));
}


int main() {
	
	scanf_s("%d", &len);
	for (int i = 0;i < len;i++) {
		scanf_s("%d", &arr[i]);
	}
	
	grape(0);
	printf("%d", MAX);

}

djm03178 4년 전 0

비슷한 아이디어라고 생각하시겠지만, 치명적인 차이가 있습니다. 바로 메모이제이션을 쓴다는 점입니다.

특정 x에 대해 grape(x)에 대한 답을 하나 구했다면, 다음에 다시 grape(x)가 호출되었을 때 그 답을 다시 구할 필요 없이 이전에 구한 답을 그대로 반환하게 하면 됩니다.

djm03178 4년 전 1

왜 지금 코드가 시간 초과인지 궁금하시다면, 코드를 아래처럼 바꾸고 다음 입력을 넣어보시고 겨우 n=20인 케이스를 처리하기 위해 얼마나 많은 함수 호출이 이루어지는지 확인해 보시면 됩니다.

#include <stdio.h>

int max(int a, int b, int c) {
	if (a > b&& a > c) {
		return a;
	}
	if (b > a&& b > c) {
		return b;
	}
	else {
		return c;
	}
}


int MAX = 0, len = 0;
int arr[10000] = { 0 };

int grape(int counter) {
	printf("%d\n", counter);
	if (counter + 4 > len) {
		return max(arr[counter] + arr[counter + 1], arr[counter + 1] + arr[counter + 2], arr[counter] + arr[counter + 2]);

	}
	MAX = max(arr[counter] + arr[counter + 1] + grape(counter + 3), arr[counter] + grape(counter + 2), grape(counter + 1));
}


int main() {

	scanf_s("%d", &len);
	for (int i = 0; i < len; i++) {
		scanf_s("%d", &arr[i]);
	}

	grape(0);
	printf("%d", MAX);

}

20
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

baraba6u 4년 전 0

오... 감사합니다. 많이배우고 갑니다^^

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

문제

문제

출처

ICPC

시간초과가 나는데 어떤 부분이 시간초과인지 궁금합니다.

baraba6u 4년 전 0

djm03178 4년 전 0

djm03178 4년 전 1

baraba6u 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말