[백준] 6064번 : 카잉 달력- JAVA [자바]

가오리·2023년 11월 29일
0
post-thumbnail

https://www.acmicpc.net/problem/6064


브루트포스 알고리즘 문제이다.

year+1 씩 해주면서 풀면 시간초과가 발생한다.

일단, year가 될 수 있는 최대 값은 MN최소공배수(GCD)라고 문제를 읽으면 알 수 있다.

그 후 시간 초과가 안나게 건너뛰면서 값을 늘리는 방법을 생각해야 한다.

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

이러한 공식을 이용해서 건너뛸 범위를 정해야겠다.

year % M == x가 되는 방법은 뭐가 있을까?

year가 M의 배수 + x 면 된다.

이것을 보고 yearM만큼씩 건너뛰면서 구할 수 있구나를 알았다.

그럼 시작하는 제일 작은 year은 무엇일까?
바로 x 이다.

즉, yearx를 대입하고, year + M을 해주면서 답을 구하면 된다.

  1. year = x의 값으로 처음에 대입해주면서 시작한다
  2. 그 이후 year % N == y 인 값을 구하면 된다.
  3. 없으면 year += M 을 해주면서 (M만큼 건너뛰면서) 답을 찾으면 된다.

이때 에외 상황이 발생한다.
N == y인 경우 답을 체크하지 못한다.

해결방법으로 나머지 공식 즉, 반복문에 들어가기 전에 xy-1 씩 해준 뒤 나중에 year 답에 +1을 해주면 된다.


public class bj6064 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            int M = Integer.parseInt(split[0]);
            int N = Integer.parseInt(split[1]);
            int x = Integer.parseInt(split[2]);
            int y = Integer.parseInt(split[3]);

            // year % M = x
            // year % N = y

            // x를 고정 -> year % M == x 인 값

            // 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 인 경우를 보자
            // year = x(12) 일 때
            // year(12) % N(6) == 0이다.
            // y(6)이 아닌 것이다.
            // 체크를 하지 못하기 때문에 이 경우를 체크하는 로직도 추가해야 한다.
            // 나머지 정리 방식을 사용하여 x와 y를 -1 씩 해주고 나중에 year에 +1을 해주면 된다.

            x--;
            y--;
            int year = x;
            while (year <= lcm) {
                // year % M == x
                // year % N == y
                if (year % N == y) {
                    bw.write(year + 1 + "\n");
                    break;
                }
                year += M;
            }

            if (year > lcm) bw.write(-1 + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int GCD(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        return GCD(b, a % b);
    }
}
profile
가오리의 개발 이야기

0개의 댓글

관련 채용 정보