[백준 | Java] 6064 카잉 달력

내 풀이

오답 풀이

이 문제는 브루트포스 문제로,
<1, 1>에서 조건에 부합할 때 까지 result에 1씩 더해주어 result를 구하려고 다음과 같이 코드를 작성했다.

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

public class _6064_카잉달력 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int i = 0; i < T; i++) {
            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 result = 0;
            int initX = 0;
            int initY = 0;

            for (int j = 0; j < 40000; j++) {
                if (initX == x && initY == y) {
                    break;
                } else if (initX == M && initY == N) {
                    result = -1;
                    break;
                } else if (initX == M) {
                    initX = 1;
                    initY++;
                    result++;
                } else if (initY == N) {
                    initY = 1;
                    initX++;
                    result++;
                } else {
                    initX++;
                    initY++;
                    result++;
                }
            }
            System.out.println(result);
        }
    }
}

정답 풀이

틀린 풀이의 로직은 정답이지만 시간초과로 오답이었다.

공통되는 수들의 최댓값을 구하면 for문을 40000번까지 돌리지 않아도 마지막 해가 M과 N의 최소공배수인 것을 알 수 있다.

이후 시간초과가 나지 않도록 건너뛸 수 있는 부분은 건너뛰면서 result를 늘려가는 방법은 다음과 같다.

1. 이 로직의 공식을 구해보면 result % M == x이고, result % N == y이다.
2. 1번을 간단히 해보면,
   x가 M만큼 증가할 때 마다 x의 값은 동일하고 y의 값만 변하고
   y가 N만큼 증가할 때 마다 y의 값은 동일하고 x의 값만 변한다.
3. 문제의 예제 1번의 경우 다음의 과정을 거친다.
   
4. 이 때 N == y일 때 i % N == y는 절대 성립하지 못하게 되기 때문에 x와 y에 각각 -1을 해준 뒤 구해진 i에 i+1을 해 답을 반환한다.
5. for문을 도는 동안 if문에서 true 값을 할당받지 못했으면 -1을 반환한다.

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

public class Main {
    static int M;
    static int N;
    static int lcm;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            LCM();

            boolean check = false;
            for (int j = x; j < lcm; j += M) {
                if (j % N == y) {
                    System.out.println(j+1);
                    check = true;
                    break;
                }
            }
            if (!check)
                System.out.println(-1);
        }
    }

    static void LCM() {
        int max = Math.max(M, N);
        int min = Math.min(M, N);

        int mod = 1;

        while (mod != 0) {
            mod = max % min;
            max = min;
            min = mod;
        }

        lcm = M*N/max;
    }
}