[백준] [6064] 카잉달력 (JAVA) (정수론) (나머지정리)

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

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

입력

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

출력

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

---

※ JAVA 코드 (카잉달력)

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

public class Main {

    static int T, N, M, X, Y, pattern, s;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());

            // input
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            X = Integer.parseInt(st.nextToken());
            Y = Integer.parseInt(st.nextToken());

            int cnt = 0;
            int make;

            int rnSeq = Math.max(N, M);
            // 증가 패턴은 N과 M중 더 작은 수
            int upSeq = Math.min(N, M);

            // N, M의 최소공배수
            int lcdVal = LCD(N, M);

            // 두 수중 더 작은 수를 기준 패턴의 시작값
            pattern = N >= M ? Y : X;
            s = pattern;

            // 기준이 되는 값 이외값이 만들어져야하는 값
            make = N >= M ? X : Y;

            // 초기 cnt값
            cnt += pattern;

            for(;;) {
                // return point
                if(s == make) {
                    System.out.println(cnt);
                    break;
                } else if(cnt > lcdVal) {
                    System.out.println(-1);
                    break;
                }

                cnt += upSeq;
                s += upSeq;

                // 증가값은 Max(N, M)을 초과하지 않는다
                if(s > rnSeq) { s = s % rnSeq; }
            }
        }
    }

    public static int GCD(int a, int b) {
        while(b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    public static int LCD(int a, int b) {
        return (a * b) / GCD(a, b);
    }
}

---

※ 생각정리 (카잉달력)

1. 패턴 생각하기

2. 종료조건 생각하기

 

먼저 값이 증가하는 패턴을 찾아야한다. 패턴을 찾기위해선 수가 일정히 증가하는 중에 값자기 변화하는 부분을 잘 살펴볼 필요가 있다. 문제에서 주어지는 예시를 통해 패턴을 찾아보자

10 12 3 9

(1, 1) (2, 2) (3, 3) (4, 4) (5, 5) (6, 6) (7, 7) (8, 8) (9, 9) (10, 10) (1, 11) (2, 12) (3, 1)

위에서 보면 10번째 까지는 일정 패턴이 유지되다가 11번째부터 일정하게 증가하는 패턴이 바뀌게 된다.

X가 만들 수 있는 최대값은 N, Y가 만들 수 있는 최대값은 M이기에 수가 넘어가면 다시 1부터 시작하게 된다. (여기선 N, M순으로 사용)

 

1) 더 작은 수를 기준으로 일정하게 반복된다. 

10과 12중 10을 기준으로 10번째 마다 수의 변화가 일어난다 -> N과 M 중 더 작은 수에 상응하는 X또는 Y가 시작점이 된다.

(1, 1) (2, 2) (3, 3) (4, 4) (5, 5) (6, 6) (7, 7) (8, 8) (9, 9) (10, 10) (1, 11) (2, 12) (3, 1)

찾아야하는 수 (3, 9)에서 앞의 수 3을 먼저 찾고 시작할 수 있다. 3번째에 존재하는 3은 N의 크기만큼 반복된다. 3, 13, 23, 33 이 반복되는 수중 Y값을 찾아주면 된다.

위 패턴을 적용하면 변동값 s는 초기값 pattern(3)을 가지며 Math.min(N, M)의 값 만큼 증가한다. 증가할때 만약 수가 Math.max(N, M)을 넘는다면 그 나머지를 대입해야하므로

s = s % rnSeq라는 패턴을 찾을 수 있다.

(1, 1) (2, 2) (3, 3) (4, 4) (5, 5) (6, 6) (7, 7) (8, 8) (9, 9) (10, 10) (1, 11) (2, 12) (3, 1)

(3, 1) = (3, 13)에서 13을 12로 나눈 나머지값인 1이된다.

s += upSeq;

// 증가값은 Max(N, M)을 초과하지 않는다
if(s > rnSeq) { s = s % rnSeq; }

 

2) 종료 기준이 필요하다

위와 같이 증가할 경우 로직의 반복수를 줄여 확실히 시간을 절약할 수 있다. 하지만 적절한 종료조건을 정하지 않는다면 무한루프에 빠질 가능 성이있기에 적절한 종료시점을 찾아야한다.

10, 12는 조금 큰 수이기에 조금 작은 수로 패턴을 찾아보자

N, M = (4, 3)인 수의 패턴은 다음과 같다

(1, 1), (2, 2), (3, 3), (4, 1), (1, 2), (2, 3), (3, 1), (4, 2), (1, 3), (2, 1), (3, 2), (4, 3) = 12개

여기서 최대로 나올 수 있는 수는 두 수의 최대 공배수 만큼인걸 알 수 있었다.

 

public static int GCD(int a, int b) {
    while(b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

public static int LCD(int a, int b) {
    return (a * b) / GCD(a, b);
}

 

바로 최대공약수, 최소공배수 코드를 작성하고 카운트가 최소공배수보다 클때 그냥 -1을 출력하도록 하였다.

 

감사합니다.