6064. 카잉 달력
[백준, 실버, c++]
문제를 보면 나머지를 가지고 뭔가 하는게 아닐 까 하는 생각이 든다.
나도 그런 생각으로 시작했다. 증가하는 수는 동일하다는 가정으로 1식 더해가면서
M과 N을 %연산을 해, x, y 에 도달하면 종료하는 코드를 생각했다.
결론은 시간초과였다. 다른 생각을 해보자.
x 와 y 중 하나를 고정해두고, 고정된 수가 다시 돌아오는 M 또는 N 을 더해가면서
1 을 더하는 대신 M 또는 N 속도로 가능하게끔 했다.
long long first_a = x - 1; // x 고정
first_a += M; // M 씩 증가
// y 가 current_b 와 같은지 확인
long long current_a = x;
long long current_b = first_a % (N) + 1;
if(current_b == y) {
cout << first_a + 1 << endl;
return;
}전체 로직 흐름
1. M 과 N 중에서 더 큰 수를 정해서 속도를 더 높인다.
if (M < N) {
play2();
} else {
play();
}2. M 또는 N 을 더하기 전에 되는지 확인한다.
long long first_a = x - 1;
long long first_current_b = first_a % (N) + 1;
if(first_current_b == y) {
cout << first_a + 1 << endl;
return;
}3. x로 시작했다면 다시 x 로 올 때까지 무한 반복
if(current_a == current_b && current_b == x) {
break;
}여기서 무한 반복 대신에 최대 공배수 까지 되도록 할 수도 있다.
유클리드 호제법을 참고하자.
int gcd(int a, int b) {
if(b == 0)
return a;
return gcd(b, a%b);
} // 핵심은 b 가 0이 될때까지 나머지를 나머지하는 것이다.정리
유클리드 호제법 을 앞으로는 혼자서 작성 할 수 있게끔 되면 좋을 것 같다.
최대 공약수는 a * b / gcd(a, b) 이다.
gcd = greatest common divisor
lcm = least common multiple