[BOJ] 6064. 카잉 달력(Java)

[BOJ] 6064. 카잉 달력(Java)

Problem

제출일 : 2020-03-10

문제 풀이 시간 : 4H

난이도 : ★★★★☆

---

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

최근에 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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

Input

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

Output

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

Example

input

3
10 12 3 9
10 12 7 2
13 11 5 6

output

33
-1
83

Solution & Inpression

나머지 연산의 특징을 이용하여 문제를 해결하였다.

x값에 M을 더하여 M으로 나누는 나머지 연산을 수행한 결과와 x를 M으로 나누는 나머지 연산을 수행한 결과가 같기 때문에 x값에 M만큼 증가시키며 해당 값이 N으로 나누었을때의 나머지가 y값과 같은지를 검사하였다.

코드상에서 (year % N) == 0 ? N : year % N 부분은 10%10의 결과가 10이 아닌 0이기에 위와같이 처리해주었다.

---

나머지 연산의 특징

a를 b로 나눈 나머지를 a mod b 할때 나머지는 다음과 같은 식들이 항상 성립합니다.

$1.\ (a+m)\mod m=a \mod m$

$ 2.\ ((a\mod m) + ( b\mod m) ) \mod m = ( a + b ) \mod m $

$3.\ ( ( a \mod m) \times ( b \mod m) ) \mod m = ( a \times b) \mod m $

Code

언어 : JAVA

메모리 : 23080 kb

실행 시간 : 352 ms

package BOJ.Math;
import java.util.Scanner;

public class Silver1_6064_카잉달력 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            int M = sc.nextInt();
            int N = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            int year = x;
            int max = lcm(M, N);

            while (true) {
                if (year > max) {
                    System.out.println("-1");
                    break;
                } else if (((year % N) == 0 ? N : year % N) == y) {
                    System.out.println(year);
                    break;
                }
                year += M;
            }
        }
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
}

Reference

6064번 : 카잉 달력|작성자 DolphaGo