[백준] no6064: 카잉달력

문제

    /**
     * M, N이 주어진다.
     * 각각 X<=M 이고, Y<=N 이다.
     * 매 년 X+1, Y+1이된다.
     * M,N과 X,Y가 주어질 때, X,Y는 몇번째 차례인지 구해라.
     * 단, X, Y가 유효하지 않다면, -1을 출력해라
     */

---

원리

1. 브루트포스

: 극한의 비효율. O(NM)이라는 시간복잡도를 가진다.

 

2. 최소공배수(LCM)를 이용한 계산방법

: 주어진 X가 나오는 경우를 M의 곱으로 반복하며 구하는 방법. 만약 결과에 도달한다면 'M * a반복 + X'만큼 반복해야함

: 또한, 반복은 최소공배수까지만 반복가능. (최소공배수의 마지노선은 M * N)

: 반복수 a * M + X 만큼의 이동에 - Y 만큼을 해준 경우를 N으로 정확히 나눠진다면, 

  앞자리가 M*a+X만큼 이동할 때,

  뒷자리가 N*a+Y만큼 이동이 가능하다는 의미임.

* 이때, 최소공배수는 유클리드 호제법을 이용해 구했다. (즉, 두 수의 곱 / 최대공약수 = 최소공배수)

* 유클리드 호제법 : 두 수의 최대 공약수를 구하는 방법으로, 두 수를 서로 나누는 작업을 반복하면서 가장 먼저 나머지가 0이 되는 수가 최대공약수가 되는 알고리즘 방법론

---

 

나의 코드

브루트포스 [ 시간초과 ]

: M, N이 최대 40000이라, 40000*40000 = 1600000000까지 일일이 계산하면 너무 많다.

private static int M;
private static int N;
private static int X;
private static int Y;

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());

    while(T-->0) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        bw.write(""+calculate()+"\n");
    }
    bw.close();
}

private static int calculate () {
    int result = -1; // 유효하지 않은 경우, -1이 출력
    int nowX = 0;
    int nowY = 0;
    int count = 0;
    int MN = M*N; // 가능한 마지막 순서

    // 앞뒤 숫자를 1씩 증가시키며 반복
    // 최대 가능 순서 혹은 목표지점 도달시 탈출
    for(int i = 0 ; i < MN ; i++) {
        nowX++;
        nowY++;
        count++;
        if(nowX>M) nowX = 1;
        if(nowY>N) nowY = 1;
        if(nowX==X && nowY==Y) {
            result = count;
            break;
        }
    }

    return result;
}

 

 

---

레퍼런스 코드

레퍼런스 코드 링크 : https://girawhale.tistory.com/10

private static int M;
private static int N;
private static int X;
private static int Y;

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());

    while (T-- > 0) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        bw.write("" + calculate() + "\n");
    }
    bw.close();
}

private static int calculate() {
    int result = -1; // 유효하지 않은 경우, -1이 출력
    int LCM = M * N / GCD(M, N); // 최소공배수 = 두 수의 곱 / 최대공약수
    int rotate = 0; // 몇바퀴 돌았는지 확인

    while (rotate * M < LCM) {
        if ((rotate * M + X - Y) % N == 0) {
            result = rotate * M + X; // 카잉달력의 앞자리 수가 몇번 반복됬는지 + X만큼의 추가이동 = 총 반복 수
            break;
        }
        rotate++;
    }
    return result;
}

/**
 * 최대공약수를 구하는 공식 (유클리도 호제법)
 *
 * @return 나머지가 0일때까지 나눠주는 방식으로, 나머지가 0이되는 수 중 가정 먼저 나온 수가 최대 공약수이다.
 */
private static int GCD(int a, int b) {
    if (b == 0) return a;
    return GCD(b, a % b);
}