BOJ6064 / 카잉 달력

BOJ6064.java

// https://www.acmicpc.net/problem/6064
// 20.8.11. ventania1680
package BOJ;

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

public class BOJ6064 {
    public static int findGCD(int m, int n) {
        while (n > 0) {
            int r = m % n;
            m = n;
            n = r;
        }
        return m;
    }

    public static void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while(t-- > 0) {
            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 gcd = m * n / (m > n ? findGCD(m, n) : findGCD(n, m));
            int tx = x, ty = x % n;
            if (ty == 0) ty = n;
            int answer = x;
            while (ty != y && answer <= x + gcd) {
                ty += (m - n);
                if (m > n) {
                    ty %= n;
                }
                else {
                    ty = Math.floorMod(ty, n);
                }
                if (ty == 0) ty = n;
                answer += m;
            }
            if (ty != y)
                answer = -1;
            sb.append(answer + "\n");
        }
        System.out.print(sb);
    }
}

 

최소공배수를 기점으로 tx, ty가 반복된다. 이를 이용하여 반복문 탈출조건을 정할 수 있다.

 

m년이 지날 때마다 y는 m - n 만큼 더해진다.  y의 범위는 1 ~ n이므로 모듈러연산을 이용하여 범위를 제한할 수 있다.

 

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

6064번: 카잉 달력

https://github.com/ventania1680/algorithm/blob/master/Algorithm/src/BOJ/BOJ6064.java

ventania1680/algorithm