[백준 6064] 카잉 달력 (JAVA)

백준 6064번 문제 - 카잉 달력

6064번: 카잉 달력

---

문제 분석 

 

•  

 

• 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다.
• 즉 해를 <x, y>라고 표현한다.
• 이때 다음규칙을 따라 x,y가 수정된다. 
  • x의 최대치는 M, y의 최대치는 N이다.
  • 이 때 x가 M을 초과할 시, x 값은 x를 M으로 나눈 나머지 값으로, y가 N을 초과할 시, y 값은 y를 N으로 나눈 나머지 값으로 설정
• N, M, 수정된 x, 수정된 y가 주어질 때, 원래 x, y값을 출력해라.

---

해결 포인트

•  
• 해당 x, y는 똑같은 숫자를 M과 N으로 나눴을때 나머지 값이다 
  • 혹은 x==M, y==N 일때, i%M == 0, i%N == 0 이면 된다.
• 이는 N과 M의 최소공배수까지 반복하면 된다.
  • 유클레드 호제법
• 전제 다 확인하면 시간초과가 발생한다.
  • i는 N이 크면 x로, M이 크면 y로 초기화한다.
  • 그리고 N이랑 M 중 작은 수 만큼 i를 더해간다.

---

코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static ArrayList<Integer>[] friends;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            int lcm = getLCM(N,M);
            int result = -1;
            for (int i = (N>M)?x:y; i <= lcm; ) {
                if((i%M == x || (x == M && i%M == 0) ) && (i%N == y || (y == N && i%N == 0) ) ) {
                    result = i;
                    break;
                }
                i += Math.min(N,M);
            }
            bw.write(result + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static int getLCM(int a, int b) {
        // 최소 공약수 구하기
        int sum = (a>=b) ? a%b : b%a;
        int gcd = Math.min(a, b);
        while(sum > 0) {
            int temp = sum;
            sum = gcd % sum;
            gcd = temp;
        }

        // 최소 공약수를 가지고 최대 공배수 구하기
        return (a/gcd) * (b/gcd) * gcd;
    }
}