백준 6064번 : 카잉 달력

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

풀이에 참고한 링크 : www.acmicpc.net/board/view/38786

내 풀이(2021.1.29.) :

#include <iostream>

using namespace std;

int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

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

	int T; cin >> T;
	for (int i = 0; i < T; i++) {
		int M, N, X, Y; cin >> M >> N >> X >> Y;
		int x = X;
		int y = X; if (y > N) y = ((y - 1) % N) + 1;
		int n = X;
		int L = lcm(M, N);
		bool found = 0;
		while (n <= L) {
			//cout << x << " " << y << endl;
			if (x == X && y == Y) {
				cout << n << endl;
				found = 1;
				break;
			}
			y += M; if (y > N) y = ((y - 1) % N) + 1;
			n += M;
		}
		if(!found) cout << -1 << endl; 
	}

	return 0;
}

x와 y를 둘 다 1씩 증가 시키니 시간 초과가 나왔다. 최악의 경우 M*N = 40000*40000 = 16초가 나오기 때문이다.

따라서 x를 고정시키고 y를 M 간격으로 증가시켰다. y가 증가될 때마다 나머지 값 계산으로 y값을 계속적으로 조절해줬다.

종말은 n이 M과 N의 최소공배수일 때이므로, 이를 while문의 조건문에 구현하였다.

다음은 M, N, X, Y가 주어지는 예시 2가지를 들어보았다.

10 12 // M N
3 9 // X Y

// x y -> n
1 1
2 2
3 3 -> 3
4 4
5 5
6 6
7 7
8 8
9 9    
10 10
1 11
2 12   
3 1 -> 13
4 2
5 3   
6 4    
7 5
8 6   
9 7   
10 8
1 9   
2 10    
3 11 -> 23
4 12 
5 1 
    
마지막 해 : M, N의 최소공배수

--------------------

13 11 // M N
5 6 // X Y

// x y -> n
1 1
2 2
3 3
4 4
5 5 -> 5
6 6
7 7
8 8
9 9
10 10
11 11
12 1
13 2
1 3
2 4
3 5
4 6
5 7 -> 18
6 8
7 9
8 10
9 11
10 1
11 2
12 3
13 4