[BOJ]6064번: 카잉달력(c++)

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

6064번: 카잉 달력

 

 

#include <iostream>
 
using namespace std;
 
int calendar(int M, int N, int x, int y)
{
    int MAX = M * N;
 
    // x에서부터 M씩 건너뛰며 계산
    // --> O(N)
    for (int i = x; i <= MAX; i += M)
    {
        if (i % N == y % N)
        {
            return i;
        }
    }
    return -1;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int T;
    cin >> T;
    while (T--)
    {
        int M, N, x, y;
        cin >> M >> N >> x >> y;
 
        cout << calendar(M, N, x, y) << '\n';
    }
 
    return 0;
}

 

시간제한이 있기 때문에, 

건너뛰기 브루트포스로 구현해주어야 한다.

 

M * N까지 모든 수를 다 계산한다면 O(MN)지만

M씩 건너 뛰면서 계산하면 O(N)으로 가능