[Java] BOJ 6064 카잉 달력

문제 

문제 링크 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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.
• 입력 데이터는 표준 입력을 사용한다. 입력은 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을 출력한다.

   

아이디어

• 카잉 달력의 기준 시간인 M과 N의 최소공배수를 구해준다. (유클리드 호제법을 이용하여)
• 그리고 i값을 (x - 1)값으로 시작점을 잡고 최소공배수 전까지 M만큼 증가시키면서 반복한다. ((x - 1)값을 시작점으로 잡는 이유는 최소공배수와 시작점이 같은 숫자일 경우, 반복문 자체가 돌아가지 않기 때문이다. => 예를 들어 M, N, x, y 값이 다 같을 경우)
• 만약 i값을 N으로 나눴을 때, 나머지가 (y - 1)이라면 (x값을 -1해줬으므로 y값도 똑같이 빼줌) 카잉 달력으로 만들 수 있다는 뜻이므로 결과값에 i값에 1을 더해준 값을 저장하고 반복문을 종료한다. (x, y값에 1을 빼줬으므로 결과값에도 1을 더해준다.)

겪은 시행착오

• 최대공약수와 최소공배수를 활용하는 문제인 것을 계속 적어보면서 뒤늦게 발견했다... (상당히 시간이 걸렸다.. ㅜ)
• 그마저도 처음에는 최소공배수가 아니라 최대공약수를 활용하는 문제인줄 알고 그렇게 풀다가 예제가 잘 맞지 않아 다시 풀었다... (ㅜㅜ)
• 그렇게 푼 코드도 처음 제출했을 때는 '틀렸습니다'가 뜨길래 당황했다.
• 예제는 다 맞았는데 왜 틀렸지하고 반례를 찾아보니 M, N, x, y가 모두 같은 숫자일 경우, 반복문을 들어가지 못해 무조건 -1을 출력한다는 것이였다. (최소공배수와 x, y가 같은 경우)
• 그래서 반복문에 들어갈 수 있도록 x, y값에 -1을 해주어 예외가 없도록 하고 결과값을 구할 때 뺀 -1을 다시 더해주도록 수정하였다.

생각보다 쉽게 풀리지 않아 힘들었던 문제였다....ㅜㅜㅜ

코드

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

public class BOJ6064 {

    static int gcd;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for(int test = 0; test < T; test++){
            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());

            // 최대공약수를 저장할 변수
            gcd = 0;
            // 최대공약수 구하기
            GCD(M, N);

            // 최소공배수를 저장할 변수
            int lcm = 0;
            // 최소공배수 구하기
            lcm = (M * N)/gcd;

            // 결과값 저장 변수
            // 해당되는 카잉 달력 년도가 없다면 -1을 출력해야되므로
            // -1로 초기화
            int result = -1;

            // x값을 기준으로 최소공배수 전까지 반복
            // i값은 x값으로 시작해서 M값만큼 계속 증가시킴
            // 최소공배수와 x, y값이 모두 같을 경우 해당 반복문을
            // 진행하지 못하므로 x, y값에 -1처리하고 돌림
            for(int i = (x - 1); i < lcm; i = i + M){
                // i값을 N으로 나눴을때, 나머지 값이 y값으로 나온다면
                if(i % N == (y - 1)){
                    // result값을 i로 저장하고
                    // 위에서 x, y값에 -1을 했으므로 + 1을 해줌
                    // 반복문 종료
                    result = i + 1;
                    break;
                }
            }

            sb.append(result + "\n");
        }

        System.out.println(sb);
    }

    public static void GCD(int n1, int n2){
        // n1이 n2로 나누어 떨어진다면 n2가 두 수의 최대공약수이므로
        // 최대공약수는 n2고 함수 종료
        if(n1 % n2 == 0){
            gcd = n2;
            return;
        }

        // 만약 나누어떨어지지 않는다면 유클리드 호제법을 이용해서
        // n2와 n1을 n2로 나눈 나머지로
        // 함수를 다시 돌림
        GCD(n2, n1 % n2);
    }
}