[백준] 6064 : 카잉 달력

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

6064번: 카잉 달력

M과 N의 최소공배수가 최대연도니까 그만큼 for문을 돌림.

year을 +1 해주면서 x 와 y 를 계산해줌. 이때 나머지가 0인 경우를 생각해야 하기 때문에 x, y를 입력할 때 -1을 해준다.

나온 year에 +1 해준 값이 답.

 

내 코드

메모리 : 44152 KB

시간 : 632 ms

코드 길이 : 1131 B

 

[내 코드]

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		while(T-- > 0) {
			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;
			
			int year = 0;
			int GCD = (M*N)/getGCD(M, N);
			int result = -1;
			
			for(int i = x; i < GCD; i += M) {
				year = i;
				
				if(year % N == y) {
					result = year + 1;
					break;
				}
			}
			sb.append(result).append('\n');
		}
		System.out.print(sb);
	}
	
	//최대공약수
	public static int getGCD(int num1, int num2) {
		if(num2 > num1)
			return getGCD(num2, num1);
		else {
			if(num1 % num2 == 0)
				return num2;
			return getGCD(num2, num1 % num2);
		}
	}
	
}

 

1등 코드

메모리 : 12604 KB

시간 : 132 ms

코드길이 : 2616 B

 

[상위권 코드]

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

public class Main {
	static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		// reader = new BufferedReader(new StringReader(str));
		int T = Integer.parseInt(reader.readLine());
		
		for (int t = 1; t <= T; t++) {
			StringTokenizer tokens = new StringTokenizer(reader.readLine());
			int M = Integer.parseInt(tokens.nextToken());
			int N = Integer.parseInt(tokens.nextToken());
			int X = Integer.parseInt(tokens.nextToken());
			int Y = Integer.parseInt(tokens.nextToken());
			
			int MaxValue = 0;
			int result = 0;
			if (M > N) {
				MaxValue = lcm(M, N);
				result = Calender(M, N, X, Y, MaxValue);
			}else {
				MaxValue = lcm(N, M);
				result = Calender(N, M, Y, X, MaxValue);
			}
			output.append(result).append("\n");
		}
		System.out.print(output);
	}
	
	static int Calender(int m, int n, int x, int y, int l) {
		int result = 0;
		int cnt = 0;
		while (result <= l) {
			result = m * cnt++;
			result += x;
			int div = result % n;
			if (div == 0) div = n;
			if (div == y) {
				return result;
			}
		}
		return -1;
	}
	
	// 뉴클리드 호제법 - 최대 공약
	static int gcd(int bn, int sn) {
		int r = bn % sn;
		if (r == 0) {
			return sn;
		}else {
			return gcd(sn, r);
		}
	}
	
	static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
	
	static String str = "3\n"
			+ "10 12 10 12\n"
			+ "10 12 7 2\n"
			+ "13 11 5 6";
}