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

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

---

[접근 방법]

 

브루트포스 알고리즘 파트이기에,

1년 부터 M, N의 최소 공배수 까지 모두 탐색하고자 하는 것을 생각하였지만, 이는 시간 제한에 막히게 되었다.

 

실행 시간 1초 = 약 2000만번 연산

(1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N)

worst case : M = 39983, N = 40_000 을 모두 탐색하는 경우
(39983은 소수)
39983 * 40000 = 약 16억 (X)

 

따라서 다른 방법을 찾아야 한다.

구하고자 하는 x을 고정 시키고 i를 +M 만큼 증가 시키며, y를 탐색하는 방법을 채택하게 되었다.

 

나머지 연산을 이용할 것인데, 이때 0이 나오는 것을 방지하기 위해 , x = x-1, y = y-1을 한 후, 결과값에 +1을 해주었다.

---

[JAVA 코드]

// 6064번 - 카잉 달력
import java.util.*;
import java.io.*;

public class Main {

    static int year;
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

            Boolean flag = false;

            // x를 고정시킨 상태에서 y만 탐색
            // i는 +M 씩만 증가하여 x값은 고정된다.
            for(int i = x; i<(M*N); i+=M){
                if (i%N == y){
                    bw.write( (i + 1) + "\n");
                    flag = true;
                    break;
                }
            }

            if (!flag){
                bw.write(-1 + "\n");
            }
            bw.flush();
        }

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

---

[Rewind]

 

1. 어려웠던 점

- 접근 방법을 찾는 것이 어려웠다.

 

2. 알게된 점

- 브루트포스 알고리즘 이여도 시간관리를 해야 한다는 것을 깨닫았다.

 

3. 개선 방향

- 비슷한 문제를 여러개 풀어야 한다.

- 수학적 논리력을 향상시켜야 한다.