백준 6064 - 카잉 달력

Java

6064 번 - 카잉 달력

문제

접근 방법

시간 초과를 생각하지 않고 해결하려면, 변수 2개를 두어 각각 하나씩 증가하며 n, m을 각각 modulo를 적용해보며 x, y와 같은지 확인하면 된다.

하지만 위 방법은 1 ≤ M, N ≤ 40,000이므로 시간초과를 유발한다.

따라서, x를 고정하고 y만 비교하는 방식으로 해결하였다.

이 말은 현재 표현하려는 해 idx를 x의 배수로하고, idx를 해당하는 m으로 modulo를 연산하여 y와 같은지 비교하면 된다.

<x:y>에 의해 표현되는 해가 없는지 확인하기 위해, M과 N의 한계인 최소공배수 LCM으로 두어서 계산하였다.

코드

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

public class Main {
	static int result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());

    	int n, m ,x ,y;
    	while(tc-- != 0) {
    		stk = new StringTokenizer(br.readLine());
    		n = stoi(stk.nextToken());
    		m = stoi(stk.nextToken());
    		x = stoi(stk.nextToken());
    		y = stoi(stk.nextToken());

    		int max = Math.max(n, m);
    		int min = Math.min(n, m);
    		int gcd = GCD(max,min);
    		int lcm = (n * m) / gcd;

    		int idx = x, tempY;
    		boolean isOk = false;

    		// x를 고정하고 y가 맞는지만 확인한다.
    		while(idx <= lcm) {
				// y가 m으로 나누어 떨어지면, m이 아닌 0으로 나오므로 삼항 연산자로 확인한다.
    			tempY = idx % m == 0 ? m : idx % m;
    			if(tempY == y) {
    				isOk = true;
    				break;
    			}
    			idx += n;
    		}

    		if(isOk)
    			System.out.println(idx);
    		else
    			System.out.println(-1);
    	}

    	br.close();
	}

	static int GCD(int max, int min) {
		if(min == 0)
			return max;
		else
			return GCD(min, max % min);
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

꽤 시간을 많이 잡아 먹은 문제였다.
x를 고정하고 y를 계산한다는 것을 생각하기 꽤 어려운 문제였다.

개선할 점