[Algorithm] 백준_6064 카잉 달력 java

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 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>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

풀이

처음에는 i를 m*n만큼 순회하면서 j % m == x && j % n == y인 경우를 출력했었다. 이렇게 하니 시간초과가 발생했고, 더 나은 풀이법을 찾지 못해 검색해서 풀었다.
참고한 풀이는 여기에서 찾아볼 수 있다.

참고한 풀이에서는 주어진 x, y에서 x만 고정값으로 두고 y가 일치하는 순간을 구해 해결했다.

1. x가 고정일 때, y값은 (x + M) % N으로 구할 수 있다.
2. count는 해의 값으로, 맨 처음은 x % (M+1)로 구한다. 그 후부터 M을 더해준다.
   M+1을 해주는 이유는 x와 M이 같을 때 count가 0이 아니라 x와 같아야하기 때문이다.
3. 구한 count가 M과 N의 최소 공배수보다 작아야한다.
   • 최소 공배수 : 두 수의 값 / 최대 공약수

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;

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

        int testCate = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCate; i++) {
            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 count = x % (m + 1);
            int tempY = x;

            for (int j = 0; j < n; j++) {
                int ty = tempY % n == 0 ? n : tempY % n;
                if (ty == y) {
                    break;
                }

                tempY = ty + m;
                count += m;
            }

            if (count > lcm(m, n)) {
                bw.write(-1 + "\n");
            } else {
                bw.write(count + "\n");
            }
        }
        bw.flush();
        bw.close();
    }

    /* 최소 공배수 */
    static int lcm(int x, int y) {
        return x * y / gcd(x, y);
    }

    /* 최대 공약수*/
    static int gcd(int x, int y) {
        while (y != 0) {
            int r = x % y;
            x = y;
            y = r;
        }
        return x;
    }
}