[Java] 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을 출력한다.

 

요약하면 1씩 늘어나는 두 숫자가 제공된 마지막 날에 도달하거나 목표 숫자에 도달할 경우 결과를 반환하라는 문제이다.

두 숫자가 1씩 늘려나가면 계산하는 브루트 포스 문제이다. 
문제를 보자마자 전에 풀었던 날짜 계산 문제가 생각이 났다.
해당 문제랑 비슷하게 달력 클래스를 만들고 계산하는 메소드를 작성하여 풀면 될거 같았다.

[Java] 1476 날짜 계산

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Kaing {
    public static void main(String[] args) throws IOException {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(rd.readLine());
        String[] values = new String[count];

        for(int i = 0; i < count; i++){
            values[i] = rd.readLine();
        }

        for(String value : values) {
            KaingCalendar kaingCalendar = new KaingCalendar(value);
            while (!kaingCalendar.comparison()) {
                kaingCalendar.numUp();
            }

            System.out.println(kaingCalendar.getYear());
        }
    }
}

class KaingCalendar{
    private boolean flag = false;

    private final int maxM;
    private final int maxN;
    private final int goalM;
    private final int goalN;

    private int M = 0;
    private int N = 0;
    private int year = 0;

    KaingCalendar(String inputString){
        String[] splitInput = inputString.split(" ");
        maxM = Integer.parseInt(splitInput[0]);
        maxN = Integer.parseInt(splitInput[1]);
        goalM = Integer.parseInt(splitInput[2]);
        goalN = Integer.parseInt(splitInput[3]);
    }

    public void numUp(){
        // 목표 숫자가 최대 값을 넘긴 상태라면 바로 종료
        if(goalM > maxM || goalN > maxN){
            setYear(-1);
            setFlag();
        }

        if(flag)
            return;

        if(++M > maxM)
            M = 1;

        if(++N > maxN)
            N = 1;

        setYear(year + 1);

        // 숫자가 원하는 목표에 도달했을 경우
        if(M == goalM && N == goalN){
            setFlag();
            return;
        }

        // 숫자가 마지막 날에 도달 했을 때
        if(M == maxM && N == maxN){
            setYear(-1);
            setFlag();
        }
    }

    public boolean comparison(){
        return flag;
    }

    public int getYear(){
        return year;
    }

    private void setFlag(){
        flag = true;
    }

    private void setYear(int newYear){
        year = newYear;
    }
}

하지만 일일이 더해서 풀어주니 시간초과가 발생했다.

 

시간을 줄일 방법을 찾아보니 규칙을 몇 개 발견했다.

x가 M만큼 증가할 때 마다 x의 값은 동일하고 y의 값만 변한다.

마찬가지로, y가 N만큼 증가할때 y의 값은 동일하고 x의 값만 변한다.

또한 결과 year이 될 수 있는 최대의 수는 m과 n의 최소 공배수이다.

 

이 규칙들을 기반으로 다시 작성했다.

문제 풀이

1. 우선 입력받은 숫자 중 M과 N을 이용해 최대 공배수를 구한다.

1-1. N * i를 M으로 나눴을 때 최초로 나머지가 0이 되는 숫자가 최소 공배수이다.

2. 입력받은 M 값에서부터 M의 최대 값을 계속 더해가면서 계산한다.

2-1. 계산한 x + (M * i) 값에서 N을 나누었을 때 나머지가 0이면 원하는 값인 것.

 

예를 들어 문제의 10 12 3 9를 구해야한다고 하자.

10과 12의 최소 공배수는 12 * i  % 10 == 0이되는 값일 때 10 * i 이다. 

i는 5 즉 최소 공배수는 60이다.

 

이때 (3+i) - 12 % 10 == 0 인수가 있다면 3+i가 원하는 년도 값이 된다.

즉 i 는 30, 답은 33이다.

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Kaing {
    public static void main(String[] args) throws IOException {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(rd.readLine());
        String[] values = new String[count];

        for(int i = 0; i < count; i++){
            values[i] = rd.readLine();
        }

        for(String value : values) {
            KaingCalendar kaingCalendar = new KaingCalendar(value);
            kaingCalendar.getYear();
        }
    }
}

class KaingCalendar{
    private final int maxM;
    private final int maxN;
    private final int goalM;
    private final int goalN;
    private int lcm;

    KaingCalendar(String inputString){
        String[] splitInput = inputString.split(" ");
        maxM = Integer.parseInt(splitInput[0]);
        maxN = Integer.parseInt(splitInput[1]);
        goalM = Integer.parseInt(splitInput[2]);
        goalN = Integer.parseInt(splitInput[3]);
    }

    // 최소 공배수 계산
    private void calculateLcm(){
        int lcm = 0;
        for(int i = 1;; i++){
            if((maxN * i) % maxM == 0){
                lcm = maxN * i;
                break;
            }
        }
        this.lcm = lcm;
    }

    public void getYear(){
        calculateLcm();

        for(int i = goalM; i <= lcm; i += maxM){
            if((i - goalN) % maxN == 0) {
                System.out.println(i);
                return;
            }
        }

        System.out.println(-1);
    }
}