글 읽기 - 이분탐색했는데 시간초과가 왜 뜰까요?

qktlf789456 3년 전 0

처음에는 그냥 풀이위주로 브루트포스로 진행하였으나 당연히 시간초과,

이분탐색이 정답이라고 해서 이분탐색으로 풀었는데 시간초과내요 ㅠ 코드에 무슨 오류가 있을까요?

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>


int current;
int need;
int *current_data;
int max = 0;
int result = 0;



int calc(int minslice, int maxslice)		//slice 단위로 자를것
{
	int slice = (minslice + maxslice) / 2;
	int remain = 0;
	

	for (int i = 0; i < current; i++)
	{
		remain += current_data[i] / slice;
	}

	if (remain >= need)		//최소값이면 갱신 후 recursive
	{
		result < slice ? result = slice : NULL;
		if(slice != maxslice-1)
			calc(slice, maxslice);
	}
	else
	{
		if(slice != minslice+1)
			calc(minslice, slice);
	}

}


int main()
{
	scanf("%d", &current);
	scanf("%d", &need);

	current_data = malloc(sizeof(int) * current);

	for (int i = 0; i < current; i++)
	{
		scanf("%d", &current_data[i]);
		max < current_data[i] ? max = current_data[i] : NULL;
	}
;


	calc(1, max);
	
	printf("%d", result);



	return 0;
}

djm03178 3년 전 0

calc 함수의 반환형이 int인데 아무것도 반환하지 않고 있습니다.

qktlf789456 3년 전 0

혹시나 해서 반환형 void 로 고쳤긴 했는데 여전히 시간초과긴하네요 ㅠ

어떤 부분이 잘못되었을까요?

line_jin 3년 전 0

재귀의 기저조건을 만족하기 못하여 무한하게 돌아가는 문제가 있을듯하네요.

기저조건을 16번 줄쪽에

if(minslice > maxslice)로 주시면 될듯합니다.

또한,

29, 34번 줄을 각각

calc(slice + 1, maxslice);

calc(minslice, slice -1);

로 주셔야 합니다.

수정후 테스트해보니 맞게 나오는군요.

팁을 드리면 기저조건은 함수의 앞부분에 적어주시는 편이 디버깅하기 편합니다.

void calc(long long minslice, long long maxslice)		//slice 단위로 자를것
{
	if (minslice > maxslice)
		return;
	long long slice = (minslice + maxslice) / 2;
	int remain = 0;

	for (int i = 0; i < current; i++)
	{
		remain += current_data[i] / slice;
	}

	if (remain >= need)		//최소값이면 갱신 후 recursive
	{
		result < slice ? result = slice : NULL;
			calc(slice + 1, maxslice);
	}
	else
	{
			calc(minslice, slice - 1);
	}

}

qktlf789456 3년 전 0

감사합니다 ㅠ slice 를 이미 한 번 계산했으니, slice 를 제외한 +1 과 -1 을 해주면서 재귀종료도 저런식으로 놓치고 있었군요 ㅠ

혹시 다른 질문드려도 괜찮을까요? 제가 짜 놓은 코드 보시면 많이 하수인가요? ㅠ 제가 어떤방식으로 공부해야하는지 궁금합니다.

백준 문제를 풀다보면 대부분 출력에 나오는 답과 똑같이 도출은 가능한데, 메모리초과, 시간초과문제가 항상 있습니다..

지금은 메모리 초과 시간초과에 너무 걱정하지 않고 문제를 보고 해결하는식에만 집중해도 괜찮을까요? 예를 들면 지금 1654랜선자르기처럼

답은 도출했지만, 완벽히 맞추기에는 시간이 오래걸려서 다른 문제를 풀고 공부하고 이런식이였거든요 ㅠ 아니면 문제 하나를 맞출때까지 완벽하게 해 나가면서 공부하는편이

더 효율적일까요?

sait2000 3년 전 1

공부 방법은 사람보다 다 다르고 저도 공부를 따로 열심히 해본 건 아니지만 제 생각을 말씀드리자면 효율도 중요하지만 결국 안되는 걸 붙잡고만 있으면 재미없어서 못 하겠더라고요. 하다보면 는다는 마음으로 하는 게 좋다고 생각합니다.

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

문제

문제

출처

ICPC

이분탐색했는데 시간초과가 왜 뜰까요?

qktlf789456 3년 전 0

djm03178 3년 전 0

qktlf789456 3년 전 0

line_jin 3년 전 0

qktlf789456 3년 전 0

sait2000 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말