[알고리즘] 백준 6064번 카잉 달력 (C++), 정수론..?

이번 문제 논리는 굉장히 어려울 줄 알았다. 어떻게든 솔루션을 발견하려고 각 값의 연관성을 찾으려 했다.

그 결과 TC에서 논리를 찾을 수 있었다.

Input
10 12 3 9
Output
33

10과 12 즉, M과 N의 차이는 +2다. x와 y의 차는 +6이다. 이를 보고, +6은 +2의 3배니까 3바퀴 정도 돌면 차이가 3배만큼 벌어질 거 같다는 생각에 10을 기준으로 3바퀴를 돌려보니 30과 30 각각의 M과 N으로 나눈 나머지는 0과 6이 나온다. (정확히 말하면 10은 3바퀴, 12는 2바퀴 돌고 6번의 해가 지난 것이다.)

 여기서 3번의 해가 더 지나면 3 9가 x, y값과 일치하면서 맞아떨어진다.

(10을 기준으로 3바퀴 돌렸으므로) 10 * 3 + (3번의 해가 지났으므로) 3 = 33

 

이 과정에서 중요한 포인트를 발견할 수 있어야 한다. 이번 문제의 논리 포인트는 나에게는 나머지였다.

위에서 시뮬레이션을 토대로 어떤 값을 각각의 M과 N으로 나누었을 때, x와 y가 되는 것을 알 수 있어야 한다.

 

그렇다면 어떤 값은 어떻게 구하며 범위는 어디까지인가

논리를 도출하여 범위를 구한 건 아니지만 10과 12일 때, 마지막 해가 60인 것을 보고 최소공배수(LCM) 임을 유추할 수 있었다.

 

이를 토대로 코드를 짜 봤다.

---

코드 (시간 초과)

x와 y가 각각 N과 M으로 같을 때는 0으로 바꿔주어야 한다.

나머지를 구하기 때문에 같은 값이 나머지로는 나올 수 없기 때문이다.

#include <iostream>
using namespace std;

int lcm(int m, int n) {
	int gcd = 0;
	if (m > n) {
		int temp = m;
		m = n;
		m = temp;
	}

	for (int i = 1; i <= m; i++) {
		if (n % i == 0 && m % i == 0) {
			gcd = i;
		}
	}

	int mIdx = m / gcd;
	int nIdx = n / gcd;

	int lcmIdx = mIdx * nIdx * gcd;
	return lcmIdx;
}

int main() {
	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;
		int lcmIdx = lcm(m, n); // 마지막 해가 최소공배수인 거 같다.
		
		bool check = 0;

		if (m == x)
			x = 0;
		if (n == y)
			y = 0;

		for (int i = 1; i <= lcmIdx; i++) {
			if (i % m == x && i % n == y) {
				cout << i << '\n';
				check = 1;
			}
		}

		if (check == 0) {
			cout << -1 << '\n';
		}
	}
	return 0;
}

하지만, 이 코드는 시간 초과를 유발한다. M과 N이 39999와 40000으로 주어질 때, 답을 도출하지만 둘의 최소공배수가 엄청 커서 for문의 연산이 엄청 커지기 때문이다.

---

이를 어떻게 해결할 것인가

찾아보니 크게 어렵진 않았다. 보고 나니 '아 이러면 되겠구나 오' 이랬다.

x의 값(나머지)이 나오도록 수를 카운트해나가면 됐었다.

즉, x의 값이 고정적으로 나오도록 수를 더해간다는 뜻

for (int i = x; i <= lcmIdx; i += m) {
	if (i % m == x && i % n == y) {
		cout << i << '\n';
		check = 1;
	}
}

x부터 시작하여 m을 더해가면 무조건 나머지는 x가 나온다.

---

문제 글이 길어 장황해지면서 논리를 떠올리기는 쉽지 않았다. 문제를 읽고서 논리를 떠올리고 싶었는데 TC를 보고, 논리를 떠올린 것이 살짝 아쉽다.

그래도 최소공배수와 나머지라는 키워드를 스스로 떠올린 것에 성취감을 느낀다.

그리고, 시간 초과를 해결하는 방법은 누가 떠올렸는지 정말 센스 있었다. 이래서 다들 정수론 정수론 하는 건가