백준 #6064

★★★★★★☆☆☆☆

문제 접근방식

처음에는 톱니바퀴를 생각했다. 톱니가 10개인 바퀴와 12개인 바퀴로 생각해서 각 바퀴가 돌아갈 때 두 수의 차이만큼씩 간격이 생길 거라고 생각했다. 이게 무슨 말이냐면 아래와 같이 생각했다.

큰 바퀴가

돌 때마다 큰 바퀴의 수를 고정해놓으면 작은 바퀴의 수는 2씩 차이가 난다. 그래서 만약 x, y가 3,9이면  차이가 6이니까 2와 2x의 차이가 6인 줄(위에 표에서 해당)에서 x와 2의 차이만큼 n에 더 해주었을 때 y와 같으면 정답일 거라고 생각했다. ex) m=12, n=10, x=9, y=3일 때  9-3=6, 위의 표에서 세 번째 줄의 6에 7을 더 해주면 3이나 온다. 이런 식의 접근을 했는데 반례가 너무 많았다. 그래서 이 로직을 더 고민하면서 몇 가지를 캐치했다. 

1. 한쪽을 고정해놓고 m만큼 더해주면 n값이 바뀌는데 이때 바뀐n값이 y와 같으면 그해가 정답이다.
2. 종말의 해로 힌트를 주었다고 생각했는데, m값을 더하는 연산의 종료조건은 m, n의 최소공배수이다.
3. 고정해놓는 한쪽을 꼭 두 수의 차이로 둘 필요가 없다는 것이다.

그래서 바꾼 로직은 고정해놓는 한쪽을 x로 두고 m씩 더해주면서 그 값이 n을 넘을 수 있으니 n으로 mod연산을 해준다.

(X+kM) mod n =y 일 때 정답,  *(X+kM) mod N이 0이 될 때 예외 처리해줘야 함.

m=12	n=10	x,y =9,3
x=9	9	9번째해
x=21	21%10=1	21번째해
x=33	33%10=3	33번째해(정답)
x=45	45%10=5	45
x=57	57%10=7	57

int GCD(int a, int b) {
    if (b == 0) {
        return a;

    }
    else {
        return GCD(b, a % b);
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> m >> n >> x >> y; //입력값 
        lcm = m * n / GCD(m, n);
        while (x <= lcm) {
            int a = (x - 1) % n + 1; //mod값이 0이 되는것을 방지
            if (a == y) {
                cout << x << "\n";
                break;
            }
            x += m;
        }
        if (x > lcm) { //해당년도가 없을때
            cout << -1 << "\n";
        }

    }
}

시간 복잡도:O(m)이다. while문이 최소공배수까지 도는데 x가 1부터 시작이라고 하고 m씩 더해주는 것인데 최소공배수는 m을 m번 더해주는 것보다 작기 때문에 m-1번까지 돌 것 같다.