BOJ 6064 카잉 달력

문제 링크

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

시간, 공간 제한

시간 : 1초

공간 : 256mb

문제 접근 방향

- M, N 이 주어 졌을 때 마지막 해는 M과N의 최소 공배수 라는 것을 파악함

- 최소 공배수와 최대 공약수를 어떻게 구하는지 찾아 봄

// 유클리드 호제법을 사용한 최대 공약수 찾기
int gcd(int a, int b)
{
	if (b == 0)
    	return a;
    return gcd(b, a%b);
 }
 
 // 최소 공배수
 // a x b = gcb(a, b) x lcm(a, b)
 // lcm = a /gcb * b
 
 int lcm(a, b)
 {
	return a / gcb(a, b) * b;
 }

- <x, y> 라면 어떤 해를  M으로 나눴을 때  x가 남고 N으로 나눴을 때 y가 남는 해를 찾아 내야 한다는 것을 알게 됨

-> 최소 공배수까지 루프 돌면서 조건에 맞는 해를 찾아 낼 수 있음

int l = lcm (a, b);
for (int i = x; i < l; i+=m) // 최소 공배수까지 모든 정수를 탐색 하지 않고 m으로 나눴을 때 나머지가 x인 수만 탐색하기
{
	// 조건 체크 : 나눴을 때 y가 남는지
    return i;
}
return (-1);

배운점

- 최소 공배수와 최대 공약수를 구하는 방법