홍장알 바로가기

문제

https://www.acmicpc.net/problem/6064

❌ 시간 초과

날짜 계산 문제를 풀었던 것처럼 브루트포스를 이용하여 풀어보고자 하였다.
그러나 이 경우 시도해보아야하는 경우의 수는 M*N, 최대 16억 개를 주어진 시간 안에 문제를 해결할 수 없다.

#include <iostream>
using namespace std;

int getGCD(int a, int b) {
	int c;
	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int getLCM(int a, int b) {
	int gcd = getGCD(a, b);
	return a * b / gcd;
}

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

	int t; cin >> t;
	while (t--) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;
		int cnt = getLCM(m, n);
		int year = 1;

		while (cnt--) {
			x--; y--;
			if (x <= 0 && y <= 0) break;

			if (x <= 0) x = m;
			if (y <= 0) y = n;
			year++;
		}
		if (cnt > 0) cout << year << '\n';
		else cout << -1 << '\n';
	}

	return 0;
}

⭕ 맞았습니다!!

브루트포스로는 해결할 수 없어 아래 나온 몇가지 조건들을 고려하여 해결하였다.

• 구하고자하는 연도를 M으로 나누었을 때 나머지가 x여야한다.
• 멸망년도에 도달하기 전까지, 구하고자하는 연도와 y값이 대응하는지 살펴본다.

#include <iostream>
using namespace std;

int getGCD(int a, int b) {
	int c;
	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int getLCM(int a, int b) {
	int gcd = getGCD(a, b);
	return a * b / gcd;
}

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

	int t; cin >> t;
	while (t--) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;
		int cnt = getLCM(m, n);
		int year = -1;

		for (int i = x; i <= cnt; i += m) {
			int ny = i % n;
			if (ny == 0) ny = n;
			if (ny == y) {
				year = i;
				break;
			}
		}
		cout << year << '\n';
	}

	return 0;
}