BOJ 백준온라인져지 6064 카잉 달력 풀이

1번째 풀이와 2번째 풀이가 있다.

1번째 풀이는 시간초과가 난다.

O(MN) = 16억번

2번째 풀이는

O(M)이다.

-1이 나오는 조건은 x가 N보다 크거나 같을때(스왑하는 과정이나 입력값이 이상할때)

정답을 구하는 방법은

앞 자리 즉 x 의 값으로 y 의 값을 찾아가는 형식이다.

M을 계속 더해줌

	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/6064
	* BOJ 백준온라인져지 6064 카잉 달력 풀이
	*/
	int lcm(int a, int b);
	int gcd(int a, int b);
	int main(){
	int T;
	scanf("%d", &T);
	while(T--){
	int M,N,x,y;
	scanf("%d%d%d%d",&M,&N,&x,&y);
	if(M > N){
	int temp;
	temp = N, N = M, M = temp;
	temp = x, x = y, y = temp;
	}
	int _lcm = lcm(M,N);
	if(x>=N) printf("-1\n");
	else{
	int result = x, tempy = x;
	while(y!=tempy&&_lcm>result){
	tempy += M;
	result += M;
	if(tempy > N) tempy %= N;
	}
	if(_lcm<result||(tempy!=y&&_lcm==result)) printf("-1\n");
	else printf("%d\n",result);
	}
	}
	return 0;
	}
	int gcd(int a, int b){
	if(a == 0)
	return b;
	return gcd(b%a, a);
	}
	int lcm(int a, int b){
	return a * b / gcd(a, b);
	}
	/* 첫 번째 풀이
	int gcd(int a, int b){
	if(a == 0)
	return b;
	return gcd(b%a, a);
	}
	int lcm(int a, int b){
	return a * b / gcd(a, b);
	}
	int main(){
	int T;
	scanf("%d", &T);
	while(T--){
	int M,N,x,y,cnt = -1,tempx=0,tempy=0;
	scanf("%d%d%d%d",&M,&N,&x,&y);
	for(int i = 0, _lcm = lcm(M,N); i<_lcm; i++){
	tempx = tempx % M + 1;
	tempy = tempy % N + 1;
	if(x == tempx && y == tempy){
	cnt = ++i;
	break;
	}
	}
	printf("%d\n", cnt);
	}
	return 0;
	}
	*/

view raw BOJ_6064.cpp hosted with ❤ by GitHub

(tempy!=y&&_lcm==result)의 조건을 안넣어서 계속 틀렸었다.

(tempy!=y&&_lcm==result)를 넣지 않으면 거의다 lcm(M,N)의 값이 뜬다.