6064번 카잉 달력

#include <iostream>
 
using namespace std;
 
int main() {
    int t, M, N, x, y;
    scanf("%d", &t);
 
    while(t--) {
        scanf("%d %d %d %d", &M, &N, &x, &y);
        int tempX = 0, tempY = 0;
        int count = 1;
        bool isExist = true;
 
        while(!(tempX * M + x == tempY * N + y)) {
            if(tempX * M + x > M * N || tempY * N + y > M * N) 
                {
                    isExist = false; 
                    break;
                }
            if(tempX * M + x > tempY * N + y) tempY++;
            if(tempX * M + x < tempY * N + y) tempX++;
        }
 
        if(isExist) printf("%d\n", tempX * M + x);
        else printf("-1\n");
    }
 
    return 0;
}

이 문제의 핵심은 어떻게해야 시간초과를 안나게 할까이다.

처음에는 문제에 주어진대로 그저 카운트를 증가시키면서 하는 방법으로 풀었지만 제출을해보니 시간초과가 나오고나서 방법을 바꾸어야겠다는 생각이 들었다.

그리고 생각해낸것이 이 문제의 사이클을 이용하는 방법이다.

x와 y는 주어진 값인 M, N을 초과하면 1로 다시 돌아간다. 하지만 둘의 사이클이 다를 수 있기 때문에 따로 생각을 해주어야한다.

따로 생각해주기 위해서 각각 다른 변수 tempX와 tempY를 선언해주고 그 값이 같다면 while문을 빠져나갈 수 있게 해준다. 그 이유는 둘의 값이 같다면 우리가 원하는 답인 몇번째 날짜인지가 답으로 나오기 때문이다. 

tempX와 tempY의 증가 시기가 조금 다른데 그 이유는 tempX * M + x 이 값과 tempY * N + y 이 두 값을 서로 비교해서 둘 중 작은 값에 있는 변수 값을 증가시켜주기 때문이다.

하지만 여기서 한번 더 생각해주어야 할 것이 -1, 즉 날짜에 포함되지 않는 경우이다.

이 경우는 최대로 나올 수 있는 몇번째에 해당하는 값이 M * N에 해당하기 때문에 이 값보다 크면 break를 걸어 빠져나올 수 있도록 한다.

보통 printf()함수나 scanf()함수를 사용할 경우 #include <cstdio>를 맨위에 넣어준다. 어쩌다보니 잊어버리고 안썼지만 잘 출력이된다.