[C++] 백준 6064번 카잉달력

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

6064번: 카잉 달력

풀이

1. 정답%M=x, 정답%N=y 라는 규칙을 활용한다.

2. 찾아야 하는 x, y는 정해졌기 때문에 x 또는 y 중 하나를 고정하고 모듈러 연산을 했을 때 x, y모두 일치하는 정답을 찾으면 된다.

M=3, N=4 일 때 <1, 2>를 찾고자 한다. x를 고정시키면 답이 될 수 있는 후보는 1, 1+M, 1+2M... 이다. 후보를 갱신할 때마다 (1+kM) % N = 2 인지 확인하면 된다. 

참고로 마지막 열의 경우 모듈러 연산이 0이기 때문에 y를 0으로 바꿔준다. 

 

리뷰

모듈러 연산을 잘 활용하자...!

#include <iostream>

using namespace std;
/* M=3, N=4
<1,1> <2,2> <3,3> <1,4> 
<2,1> <3,2> <1,3> <2,4>
<3,1> <1,2> <2,3> <3,4>
*/
int T, M, N, x, y;
int m, n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("input.txt", "r", stdin);

    cin >> T;
    for (int i=0; i<T; i++){
        cin >> M >> N >> x >> y;
        
        // res%M = x, res%N = y
        int res=x; // x 고정
        y %= N; // y가 N과 같을 때 0으로 만들기
        while ((res <= M*N) && res%N != y)
        {
            // 정답 후보는 M씩 증가하면서(x고정) y 확인
            res += M;
        }
        if (res > M*N) cout << -1 << endl;
        else cout << res << endl;
        
    }
    return 0;
}