글 읽기 - 어디서 시간초과가 나는지 모르겠습니다.

minjea917 6년 전 0

작동 방식은 이렇습니다.

x를 기준으로 수를 올리면서 그 값에 search_y를 빼고, Maximum_Y을 나눌 때, 나누어 떨어지면 참

연산 횟수가 최대 X,Y를 곱한 값보다 크면 -1을 출력하도록 했습니다.

ex)

10 12 3 9

13 (13-9)% 12 => 4

23 (23-9)% 12 => 2

33 (33-9)% 12 => 0 (참)

X,Y 를 40000, 39999로 주고 돌려봤는데도 시간초과가 나오는 부분은 없었는데

코드를 제출하면 시간초과가 뜹니다.

어디가 잘못된 것인지 알고 싶습니다 ㅠㅠ

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

// 최대 날짜 X, 최대 날짜 Y, 찾을 날짜 x, 찾을 날짜 y
int kaing(int Maximum_X, int Maximum_Y, int search_x, int search_y)
{
	int count = 1;
	int x_temp, y_temp; // x를 기준으로 계산
	int max = Maximum_Y * Maximum_X; // 최대 계산 수
	if (search_x == 1 && search_y == 1)
	{
		printf("1\n");
		return 0;
	}
	while (1)
	{
		x_temp = Maximum_X*count + search_x;
		y_temp = (x_temp - search_y) % Maximum_Y;
		if (count > max)
		{
			printf("-1\n");
			return 0;
		}
		if (y_temp == 0)
		{
			printf("%d\n", x_temp);
			return 0;
		}
		count++;
	}
	return 0;
}

int main()
{
	int testcase;
	int *Maximum_X, *Maximum_Y, *search_x, *search_y;

	scanf("%d", &testcase);

	Maximum_X = (int *)malloc(sizeof(int) * testcase);
	memset(Maximum_X, 0, sizeof(int) * testcase);
	Maximum_Y = (int *)malloc(sizeof(int) * testcase);
	memset(Maximum_Y, 0, sizeof(int) * testcase);
	search_x = (int *)malloc(sizeof(int) * testcase);
	memset(search_x, 0, sizeof(int) * testcase);
	search_y = (int *)malloc(sizeof(int) * testcase);
	memset(search_y, 0, sizeof(int) * testcase);

	for (int i = 0; i < testcase; i++)
	{
		scanf("%d %d", &Maximum_X[i], &Maximum_Y[i]);
		if (Maximum_X[i] > 40000 || Maximum_X[i] < 1 
			|| Maximum_Y[i] > 40000 || Maximum_Y[i] < 1)
			return 0;
		scanf("%d %d", &search_x[i], &search_y[i]);
		if (search_x[i] > Maximum_X[i] || search_y[i] > Maximum_Y[i])
			return 0;
	}
	
	for (int i = 0; i < testcase; i++)
		kaing(Maximum_X[i], Maximum_Y[i], search_x[i], search_y[i]);

	free(Maximum_X);
	free(Maximum_Y);
	free(search_x);
	free(search_y);
	return 0;
}

3587jjh 6년 전 1

시간초과가 안나오는 코드인데 시간초과가 뜬다면 무한루프가 있는지 한번 보세요

ho94949 6년 전 1

40000, 39999에서는 답이 확실히 나옵니다.

시간 초과가 나는 경우는 답이 -1인 경우입니다. 답이 -1인 경우는 언제가 있을까요? 그리고 왜 시간초과가 날까요? 생각해 보시길 바랍니다.

참고로 코드가 무한루프에 빠지지는 않습니다.

minjea917 6년 전 0

코드 동작 방식을 곱셈에서 덧셈으로 바꾸고, 조건 수정해주니 됐네요. 감사합니다!

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

문제

문제

출처

ICPC

어디서 시간초과가 나는지 모르겠습니다.

minjea917 6년 전 0

3587jjh 6년 전 1

ho94949 6년 전 1

minjea917 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말