백준 [6064] 카잉 달력 (JAVA)

문제

풀이

문제 그대로 구현을 한다면 시간 초과가 발생한다.

 

나머지 정리와 조금의 응용이 필요했다.

year가 될 수 있는 최대 값은 M, N의 최소 공배수가 될 수 있다.

 

최소 x 부터 시작하여 M, y 부터 시작하여 N을 만족해야 한다.

1. year % M = x
2. year % N = y

위 두 조건을 만족하여아 하는데 다르게 말하면 year가 M의 공배수 + x 이면 된다.

그래서 최소 year = x부터 M만큼 증가시키면 1번 조건을 만족하고 그 떄의 year % N == y이면 위 두 조건을 만족할 수 있다.

 

하지만 한가지 예외가 10 12 10 6 인 경우 즉, 마지막 해와 N이 같은 경우 답을 체크하지 못함

그래서 반복문에 들어가기 전 x와 y에 -1씩 해준 뒤 나머지 정리를 수행

마지막 출력 때 year + 1을 출력

정답코드

package com.baekjoon.p6064;

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

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

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

        while (T-- > 0) {
            int M, N, x, y;

            StringTokenizer st = new StringTokenizer(br.readLine());

            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            // year의 최대 값은 문제에 나와있는 것처럼 = M, N의 lcm 이다.
            int lcm = M * N / gcd(M, N);

            // 1. year = x의 값으로 처음에 대입해주면서 시작하면
            // 2. year % M == x 는 확정으로 시작한다.
            // 3. 그 이후 year += M 을 해주면서 (2번 문항을 지키기 위해)
            // 4. year % N == y 인 값을 구하면 된다.

            // 이때 12 6 12 6 인 경우(같은 경우)
            // 즉, N == y 인 경우 예외 발생
            // 체크를 하지 못하기 때문에 이 경우를 체크하는 로직도 추가해야 한다.
            // 나머지 정리 방식을 사용하여 x와 y를 -1 씩 해주고 나중에 year에 +1을 해주면 된다.

            x--;
            y--; // 이게 이해가 안되었음
            int year = x;
            while (year <= lcm) {
                // year % M == x
                // year % N == y
                if (year % N == y) {
                    sb.append(year + 1 + "\n");
                    break;
                }
                year += M;
            }

            if (year > lcm)
                sb.append(-1 + "\n");
        }

        System.out.println(sb);
    }

    static int gcd(int a, int b) {
        if (a % b == 0) {
            return b;
        }

        return gcd(b, a % b);
    }
}