백준 6065 카잉 달력 (Java)

1. 문제 링크

6064번: 카잉 달력

2. 문제 및 입출력예제

 

3. 문제 풀이

처음에는 다른 문제 풀듯이 연도를 +하면서 했더니 시간 초과라는 결과가 나왔다.

 

그래서 반복문의 횟수를 조금이라도 줄이려고 최소공배수를 구해서 돌렸지만

역시나 시간 초과..가 발생했다.

 

반복문 안의 내용을 효율적으로 돌리기 위해 갖가지 방법을 생각해보다

x를 M만큼 더하면서 그때의 연도%N이 y가 되는지 확인해봤고

그래도 틀린 답이 나오는 경우가 있어서 예시를 생각하면서 하나씩 생각해보니까

시작이 1 1이어서 나머지 계산을 정확하게 하려면 각자 -1을 해야한다는 것을 깨달았다..

 

그렇게 한참이 걸린 코드이다. 

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		int M = 0, N = 0, x = 0, y = 0;
		for (int t = 0; t < T; t++) {
			String[] split = br.readLine().split(" ");
			M = Integer.parseInt(split[0]);
			N = Integer.parseInt(split[1]);
			x = Integer.parseInt(split[2])-1;
			y = Integer.parseInt(split[3])-1;
			int m = M;
			int n = N;
			int temp;
            
            // 최대공약수
			while (m > 0) {
				temp = n;
				n = m;
				m = temp % m;
			} 

			temp = M * N / n; // 최소공배수
			boolean flag = false;
			for(int i=x;i<temp;i+=M) {
				if (i%N == y) {
					flag = true;
					System.out.println(i+1);
					break;
				}
			}
			
			if (!flag) {
				System.out.println(-1);
			}
		}

		System.out.println(sb);
	}
}