[백준] C++ 알고리즘 6064번 - 카잉 달력 문제

문제

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

6064번: 카잉 달력

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
        x -= 1;
        y -= 1;
        bool check = false;
        for (int i = x; i < (m * n); i+=m) {
            if (i % n == y) {
                cout << i + 1 << "\n";
                check = true;
                break;
            }
        }
        if (!check) cout << -1<<"\n";
    }
}

해설

먼저 나머지 연산을 통해 해결해야 한다는 생각이 들어서, X,Y의 값들을 일단 -1씩 해주었습니다.

경우의수는 M*N 즉 16억정도가 되는데, 이걸 전부다 할 수 없다.

i*M+x = 해당 해를 구하는 방법을 이용하여 구한다.

 

그리고 x, y 둘중 하나의 값을 고정 시켜 경우의 수를 O(N)으로 줄일 수 있다.

for문에서의 반복문은 x 값을 고정 즉 나머지가 계속해서 x가 나오도록 설정해주고

y의 값을 비교하여 출력한다.