[백준 C++] 6064 카잉 달력 - 정수론

6064번: 카잉 달력

#include <iostream>
using namespace std;

int GCD(int A, int B)
{
	if (B == 0)
	{
		return A;
	}

	return GCD(B, A % B);
}

int LCM(int A, int B)
{
	return (A * B) / GCD(A, B);
}

void Test()
{
	int M, N, X, Y;
	cin >> M >> N >> X >> Y;

	int MaxYear = LCM(M, N);
	for (int Year = X; Year <= MaxYear; Year += M)
	{
		int Remainder = Year % N;

		if (Remainder == 0)
		{
			Remainder = N;
		}

		if (Remainder == Y)
		{
			cout << Year << '\n';
			return;
		}
	}

	cout << -1 << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		Test();
	}
}

---

 

정수론 (나머지 정리) & 브루트포스 알고리즘 유형의 문제입니다.

 

구하고자 하는 해는 해당 년도를 M, N으로 나누었을 때의 나머지가 각각 X, Y와 같을 경우가 됩니다.

이를 구하기 위해서 Year를 증가시켜 가면서 해당 조건에 맞는 값을 탐색해야 하는데

이때 Year를 1씩 증가시킬 경우 시간 초과가 발생합니다.

 

그래서 Year를 M으로 나누었을 때 나머지가 X라고 고정을 한 후

Year를 M씩 증가시키고, Year를 N으로 나누었을 때의 나머지가 Y와 같은지만 확인하면 됩니다.

 

구현 시 주의할 점이 두 가지 있습니다.

1. 탐색 범위는 종말의 해까지 지정해야 합니다. 종말의 해는 M과 N의 최소공배수로 나타낼 수 있습니다.

2. Year가 N의 배수가 될 때 N으로 나누면 나머지가 0이 되기 때문에 나머지를 N으로 바꿔주어야 합니다.