😭백준 6064 - 카잉 달력

문제 설명

 

 

=> 브루트 포스 문제입니다. 

=> 시뮬레이션 문제로 생각하여 모든 경우의 수를 확인할 경우 시간 초과의 덫에 걸리게 됩니다. 

=> 우선 x를 맞춰두고 그 이후에 맞는 y가 있는지 확인하여야 합니다. 

=> 찾은 값이 두 수의 최소공배수를 넘지 않도록 유의하여야 합니다. 

 

 

 

 

 

최소공배수를 구하는 식은 최대공약수를 구하는 식의 도움을 받습니다.

저는 유클리드 호제법을 사용하였습니다.

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);
}

 

 

 

 

 

<code>

#include <iostream>
#include <algorithm>
#include <string>

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 Kaiing(int M, int N, int x, int y)
{
    int ans;
    
    int Tlcm= lcm(M,N);
    
    for(int i=x; i<Tlcm; i+=M)
    {
        int temp = ( i % N == 0) ? N : i % N;
        ans = i;
        if (temp == y)
        {
            return i;
        }
    }
    if( ans > Tlcm)
    {return -1;}
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    
    int TC;
    cin >> TC;
    
    for(int i=0; i<TC; i++)
    {
        int M,N,x,y;
        cin >> M >> N >> x >> y;
        
        cout << Kaiing(M, N, x, y)<<'\n';
    }
    
}

 

 

실행화면

---

=> 저 역시 제대로 이해하지 못한듯하여 다시 봐야 할 문제입니다.