[백준] 6064번: 카잉 달력

문제링크 : https://www.acmicpc.net/problem/6064

 

문제풀이

규칙찾는 데 좀 시간이 걸렸던 문제.. 규칙을 찾고 나면 쉬운 문제인 것 같다.

 

N = 6, M = 7 을 입력받은 경우로 해를 나열해보면 아래와 같다.

x = 3 입력값을 받았다고 가정하였을 때, 아래와 같은 규칙을 찾을 수 있다.

x가 3일 때 나오는 해는 x에 N을 더해서 구할 수 있고,

x가 3일 때 나오는 y값들은, 앞에서 구한 해를 M으로 나눈 나머지와 같다.

 

이를 이용해 y 입력값과 같은 값이 나올 때 까지 반복하여 해를 구한다.

 

마지막 해는 문제에서도 힌트를 줬듯이, N과 M의 최소공배수와 같다.

따라서 N과 M의 최소공배수보다 큰 경우는 유효하지 않으므로 -1을 출력한다.

 

 

소스코드

/*
 * 백준 6064번: 카잉 달력
 */

#include <iostream>
#include <string>

using namespace std;

int gcd(int a, int b);
int lcd(int a, int b);

int main() {
	int T;
	cin >> T;

	while (T--) {
		int M, N, x, y;
		cin >> M >> N >> x >> y;

		int year = x;
		int temp_y = 0;
		int l = lcd(M, N);
		while (true) {
			temp_y = year % N == 0 ? N : year % N;
			
			if (temp_y == y) break;
			if (year > l) break;	// N과 M의 최소공배수보다 큰 경우

			year += M;
		}

		year = year > l ? -1 : year;
		cout << year << endl;
	}

	return 0;
}

// 최대공약수
int gcd(int a, int b) {
	int r = 0;

	while (b > 0) {
		r = a % b;
		a = b;
		b = r;
	}

	return a;
}

// 최소공배수
int lcd(int a, int b) {
	return a * b / gcd(a, b);
}