[BOJ] 6064번 - 카잉 달력(JAVA)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

중국인의 나머지 정리 참고 블로그
https://blog.joonas.io/23

중국인의 나머지 정리 - 이해하기 쉬운 설명

 

나머지 연산을 사용해보려고 했지만 어려워서 구현 실패

그래서 문제 풀이 블로그를 참고했는데 여기서 내가 이해한 부분을 정리하기 위해 글을 작성

 

문제풀이 참고 블로그
https://girawhale.tistory.com/10

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

---

 

1. 현재 조건에서 구할 수 있는 마지막 해

    예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

   위와 같이 문제 예시에서 볼 수 있듯이 마지막 해는 M과 N의 최소공배수이다.

   즉, 마지막 해를 넘기기 전까지 해를 구할 수 있으면 답 출력 / 못 구하면 -1 출력

 

2. 표현식 정리

x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1

   x가 M보다 작으면 1씩 증가하다가 M보다 큰 수가 되면 x는 다시 1로 돌아간다. y도 x와 같다.

   이는 우리가 나눗셈을 하고 구한 나머지가 이와 같은 특징을 가진다.

a / b = c ... d
이를 말로 표현하면 a 나누기 b의 몫은 c 이고 나머지는 d 이다.

현재 우리가 가지고 있는 값으로 표현해 보면
a / M = c ... x   ---①
a' / N = c' ... y   ---②

이때, 중요한 것은 우리가 구할 값은 a 와a' 인데 a = a' 인 것을 구해야한다. (지금부터는 result로 표현한다.)
① result = M * c + x
② result = N * c' + y

즉, M * c + x = N * c' + y 이다.

 

3. 코드에 사용

int last = lcm(M, N); //가장 마지막 연도 - 최소 공배수로 구한다.
int n = 0; // M의 몫
int result = -1; //구해야 할 값

while(n * M < last){
    if((n * M + x - y) % N == 0) {
        result = n * M + x;
        break;
    }
    n++;
}

//결과 저장
sb.append(result).append("\n");

• result를 -1로 초기화한 이유
  • while문 속 조건에 만족하지 않고 끝나면 <x:y> 가 유효하지 않다는 의미
• n * M < last 
  • 현재 조건에서 구할 수 있는 마지막 해(위의 설명 참고)
  • 문제 조건 : 1 ≤ x ≤ M 이다.
  • 즉, last보다 무조건 작은 이유는 n * M + x 이므로 n * M 와 last 같을 수 없다.
• n * M + x - y
  • M * n + x = N * c' + y (위의 식 정리 참고) ----(1)
  • N * c' = M * n + x - y
  • (M * n + x - y) % N == 0 이라면 (1)식 성립한다는 의미

---

🍀 풀이 코드 🍀

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

public class BOJ6064 {
    //최대공약수
    public static int gcd(int num1, int num2){
        int tmp = 0;
        while(num2 > 0){
            tmp = num1 % num2;
            num1 = num2;
            num2 = tmp;
        }
        return num1;
    }

    //최소공배수
    public static int lcm(int num1, int num2){
        return num1 * num2 / gcd(num1, num2);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int testcase = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        for(int i = 0; i < testcase; i++){
            st = new StringTokenizer(bf.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 last = lcm(M, N); //가장 마지막 연도
            int n = 0;
            int result = -1;
            while(n * M < last){
                if((n * M + x - y) % N == 0) {
                    result = n * M + x;
                    break;
                }
                n++;
            }
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}