[백준 C++] 6064번: 카잉 달력

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

 

브루트 포스를 이용하여 문제를 해결해보았다. 전에 풀었던 문제와 비슷하지만 다른점은 유효하지 않은 답에 한해서는 -1을 반환한다는것이므로 while문을 사용하여 처리하면 오류가 발생한다. for을 이용하여 범위를 정해주어야 하는데 어떤경우에 유효하지 않은지 살펴보자

 

m, n, x, y가 각각 10 12 7 2일때 유효하지 않다. 이유는 x와 y모두 짝수 이기때문에 60갑자와 비슷한 경우인데 갑오년은 가능하지만 갑미년은 없는 이유라고 볼 수 있다. 둘다 짝수 이거나 둘다 홀수일 때 가능하고 하나가 홀수 이고 하나가 짝수인경우는 불가능하다.

 

이를 파악하기 위해서 카잉 달력의 마지막 해를 알아야하는데 <m:n>이 카잉달력의 마지막 해라고 한다. 그렇다면 마지막 해를 지나서 까지 맞는 결과값이 없다면 -1을 리턴해주면 되게끔 코드를 짜보았다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	int test_case;
	cin >> test_case;
 
	for (int T = 1;T <= test_case;T++) {
		int m, n, x, y, a = 1, b = 1, ans = 1;
		bool bo = true;
		cin >> m >> n >> x >> y;
 
		while (bo) {
			if (x == a && y == b)
				break;	
 
			if (a == m && b == n)
				bo = false;
 
			if (a < m)
				a++;
			else
				a = 1;
 
			if (b < n)
				b++;
			else
				b = 1;
 
			ans++;
		}
		if (!bo)
			ans = -1;
 
		cout << ans << '\n'; 
	}
 
	return 0;
}

 

결과는 시간초과... 1씩 증가시키는 방법말고 다른 방법으로 문제를 풀어야한다.

 

최대공약수랑 최소공배수를 이용하여 풀어주었다.

 

#include <iostream>
#include <algorithm>
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);
}
 
int main(int argc, char* argv[])
{
 
	int test_case;
	cin >> test_case;
 
	for (int T = 1;T <= test_case;T++) {
		int m, n, x, y, ans = -1;
		cin >> m >> n >> x >> y;
		int maxi = lcm(m, n); // 마지막값
 
		for (int i = x; i <= maxi; i += m) {
			int ny = i % n; // y값
			if (ny == 0) // 이때는 y가 최대값이 됨
				ny = n;
 
			if (ny == y) { // 정답
				ans = i;
				break;
			}
		}
 
		cout << ans << '\n'; 
	}
 
	return 0;
}

 

이것도 다시풀자