[백준 *Java] - 카잉 달력 (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을 출력한다.

 

---

👇  접근방식(내생각 정리)

문제를 읽으면서 생각보다 쉽게 설명해줘도 괜찮을 거 같은데, 
굳이 이렇게 길게 설명을 한 이유를 잘 모르겠네요...
설명하자면,
M, N 을 그냥 다시 1로 돌아가는 변환점을 가리키는 숫자라고 생각을 했습니다.
예제 입력 1번 중에 1행을 가지고 설명을 하자면,
10 12 3 9는
M = 10 / N = 12 / x = 3 / y = 9 입니다.
<10:12 > 기준으로하는 <3:9> 일 때의  아래의 표로 설명을 드리겠습니다.

x	y	출력	x	y	출력
1	1	1	10	8	20
2	2	2	1	9	21
...	...	...	..	...	...
10	10	10	5	1	25
1	11	11	...	...	...
2	12	12	10	6	30
3	1	13	1	7	31
4	2	14	2	8	32
...	...	...	3	9	33

이런 식으로 값을 찾으면 됩니다.

출력값 % M = x
출력값 % N = y
라는 규칙을 찾을 수 있습니다.
여기서 출력 값을 구하기 위해서,
출력값 % 10 = 3
출력값 % 12 = 9
를 가지고, 3과 9를 만족 시킬 수 있는 값을 계속 루프를 돌면서 찾는 로직을 구현할 생각입니다.

---

음..생각한 로직대로 문제를 풀었더니, 시간초과가 떴습니다..

아래는 실패한 코드인 시간초과가 뜬 로직입니다. 역시 이렇게 쉽게 풀릴리가 없죠.

아래 코드는 시간 복잡도가 O(M*N) 으로 시간제한인 1초가 넘게 됩니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int count = 1;
        for (int i = 0; i < T; i++) {
            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 max = M * N;
            while (true) {
                if (count % M == x && count % N == y) break;
                if (count > max)  {
                    count = -1;
                    break;
                }
                count++;
            }
            System.out.println(count);
        }

    }
}

 

시간을 줄이기 위해서 계속 생각하다가, 생각이 나질 않아 다른 분 코드를 참고했습니다.

시간단축을 하는 로직은

x를 먼저 맞추고, y를 따라가게 하는 것입니다.

x를 맞추면, y만을 신경쓰면 됩니다.

즉,

y는 M 만큼 증가하고 N으로 나머지 연산을 한다면 y값을 알 수 있습니다.

이런식으로 y 를 M 만큼 증가시키다보면, y 또한 맞춰질 것입니다.

 

그리고 여기서 놓치고있던 부분이 있었습니다.

문제를 보면, 10, 12 의 최소공배수는 60이라 했습니다.

이 말은 M과 N의 최소공배수를 넘는다면 예외라고 볼 수 있습니다.

 

아래에는 성공한 코드입니다.

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

public class Main {

    static int lcm(int M, int N) {
        return M * N / gcd(M, N);
    }

    static int gcd(int M, int N) {
        while (N != 0) {
            int r = M % N;
            M = N;
            N = r;
        }
        return M;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            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 year = x % (M + 1); // x와 M이 같을 때는 cnt 0이 아닌, x와 같아야하기 때문에, 맨 처음 값을 이런식으로 초기화 시켜줍니다.
            int tmp = x; // 초기에 x를 고정
            int checkPoint = N; // 루프 길이를 x 고정을 통해 y를 찾으니, y 길이로 세팅을해줍니다.
            while (checkPoint-- > 0) {
                int target = tmp % N == 0 ? N : tmp % N; // tmp 에 연산처리해주다가, N으로 나누었을 시 나온 값이 y 값일 경우를 찾음.
                if (target == y) break; // y를 찾았다면 return

                tmp = target + M; // tmp 연산처리 매 루프 시, M을 더해줍니다.
                year += M; // 매 로프마다 기준이 M이니 year 에 M을 추가
            }

            // 예외를 잡아줍니다. 유효하지 않은 표현일 때를 위해 최소공배수를 구하여 그보다 높을 시, 예외
            if(year > lcm(M, N)) System.out.println(-1);
            else System.out.println(year);
        }

    }
}

 

이 문제는 시간초과를 해결해야하는 문제라, 문제를 잘 읽고 효율이 좋은 로직을 설계하는게 중요했던 거 같습니다.

확실히 알고나니깐, 쉽다고 느껴지네요..:(