글 읽기 - 시간 초과는 대체 뭘 손봐야되는건가요 ㅠㅠ

djyoon0223 7년 전 0

이렇게 간단한 코드에 시간초과가 나올 일이 대체 어디에 있는지 ㅠㅠ

#include <iostream>
using namespace std;

int main ()
{
	int CT;
	int M, N, x, y;
	int flag = 0;

	cin>>CT;
	int* rst = new int[CT];

	for (int i = 0 ; i < CT ; i++)
	{
		cin>>M>>N>>x>>y;
	
		flag = 0;
		rst[i] = 0;

		for (int m = 1, n = 1 ; m != M || n != N ; m++, n++)
		{
			if (m > M)
				m = 1;

			if (n > N)
				n = 1;

			rst[i]++;
			
			// <m:n> = <x:y>
			if (m == x && n == y)
			{
				flag = 1;
				break;
			}
		}

		if (flag == 0)
			rst[i] = -1;
	}

	for (int i = 0 ; i < CT ; i++)
		cout<<rst[i]<<endl;

	return 0;
}

nuclear852 7년 전 0

포문을 지금 1일마다 계산하시고 계시는 데 이럴 경우 TimeComplexity가 최대 O(MN)이 될 수 있어요!

조건을 좀 더 생각해주시면 O(N)만에 수행할 수 있답니다.

힌트는 모듈러를 이용하세요.

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

문제

문제

출처

ICPC

시간 초과는 대체 뭘 손봐야되는건가요 ㅠㅠ

djyoon0223 7년 전 0

nuclear852 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말