[BOJ] 백준 6064 카잉 달력

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

 Input 

3

10 12 3 9

10 12 7 2

13 11 5 6

 

 Output 

33

-1

83

 

카잉 달력의 표기 방식은 다음과 같습니다.

첫 번째 해 <1 : 1>, 두 번째 해를 <2 : 2>로 표현

즉, <x : y>의 다음 해를 <x' : y'> 방식으로 표현합니다. 

 

1 ≤ x ≤ M, 1 ≤ y ≤ N일 때, 

만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 

만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 

<M : N>은 달력의 마지막 해.

[M = 10, N = 12인 경우]

- 첫번째 해는 <1 : 1>

- 11번째 해는 <1 : 11>

- 13번째 해는 <3 : 1>

- 마지막 해는 <10 : 12>으로 60번째 해

(x,y)가 있으면 (x+1, y+1) → (x+2, y+2) → ... 방식으로 증가합니다.

x > M이면 x = 1 / y > N이면 y = 1 시작합니다.

(※ 단순히 for문을 이용해서는 시간제한을 만족하지 못합니다.)

 

Case: <M : N> = <10, 12> ← 60번째 해

x = 3이 되기 위해서는 3 → 13 → 23 → 33 ...  

▶ 10x - 7 (M=10에 대한 등차수열)

y = 9가 되기 위해서는 9 → 21 → 33 → 45 ... 

▶ 12x - 3 (N=12에 대한 등차수열) 

마지막 해(=60번째) 이전에 공통된 해 33을 출력 

 

x = 7이 되기 위해서는 7 → 17 → 27 → 37 → 47 → 57 ...

▶ 10x - 3 (M=10에 대한 등차수열) 

y = 2가 되기 위해서는 2 → 14 → 26 → 38 → 50 ... 

▶ 12x - 10 (N=12에 대한 등차수열)

마지막 해가 60이기에 <7 : 2>는 유효하지 않는 표현입니다.

 

[구현]

(M, N)이 의미하는 『몇 번째 해』는 M,N의 최소 공배수

※ 두 수 A, B가 주어질 때 최소 공배수 = A * B / GCD(A, B)

※ 최대공약수 GCD(A, B)는 유클리드 공식을 이용

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws Exception {    
        Scanner sc = new Scanner(System.in);
         
        int T = Integer.parseInt(sc.next());
        int[] answer = new int[T];
         
        for(int i=0; i<T; i++) {
            int M = Integer.parseInt(sc.next());
            int N = Integer.parseInt(sc.next());
            int x = Integer.parseInt(sc.next());
            int y = Integer.parseInt(sc.next());
             
             
            // 최소공배수를 통해 종말 해를 구한다.
            int Max = LCM(M, N);
             
            int ix = 0, iy = 0;
            while(true) {
                // 등차수열형태로 일반화 한다.
                int temp_x = M * ix + x;
                int temp_y = N * iy + y;
                 
                // 두 값중 하나라도 Max보다 커지면 카잉 달력으로 표현할 수 없다.
                if(temp_x > Max  || temp_y > Max ) {
                    answer[i] = -1;
                    break;
                }
                // 만족할 때까지 두수들을 번갈아가면 증가시킨다.
                if(temp_x == temp_y) {
                    answer[i] = temp_x;
                    break;
                }else { // 두 값이 다르면 ix, iy를 올려가면 대조해야 한다.
                    if(temp_x < temp_y) {
                        ix++;
                    }else {
                        iy++;
                    }
                }
            }
        }
        for(int i=0; i<T; i++) {
            System.out.println(answer[i]);
        }
    }
     
    private static int LCM(int a, int b) {
        // a > b보다 크도록 배치
        if(a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        return a * b / GCD(a, b);
    }
 
    private static int GCD(int a, int b) {
        // 나누어 떨어질 때 까지
        while(a % b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return b;
    }
}