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

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

6064번: 카잉 달력

 

문제 분석을 하자면 현재 달력의 각 자리수는 m,n 까지 해마다 1씩 증가하다 1로 돌아가는 방식으로 진행이 되고

임의의 자리수가 주어졌을때 몇번째 해인지 구하면 되는 문제이다.

 

이 문제를 풀때의 아이디어는 m,n의 최소공배수가 곧 달력이 초기화 되는 한 사이클이라는 점이다.

 

그리고 임의로 주어진 수를 시작점으로 두고 각각 m,n을 더하기를 반복해

임의의 수 a, b가 같아지는 시점이 구하려는 답이된다.

 

이때 한 사이클이 지나도록 같아지는 시점이 없다는 잘못된 데이터가 주어진 경우이므로  -1을 출력해주면 된다.

 

그럼 먼저 유클리드 호제법을 사용한 최대공약수를 구하는 메소드를 만들어 최소공배수를 구해 한 사이클을 구해주겠다.

 

	static int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a%b);
	}

 

 

유클리드 호제법은 아래 포스팅에서 다뤄두었다.

 

https://0bliviat3.tistory.com/33

유클리드 호제법(JAVA)

 

 

다음으로는 유클리드 호제법으로 구한 한 사이클내에서 답을 낼때는 리턴

아닌경우 -1을 리턴해주는 메소드를 만들어준다.

단 이때 a와 b가 같은경우는 min(m,n) 이하인 첫 순회의 경우만 해당되므로 바로 리턴해주도록 한다.

 

	static int getYear(int m, int n, int a, int b) {
		if(a == b) return a;
		int max = (m*n)/gcd(m,n);
		int now = Math.min(a, b);
		while(now <= max) {
			if(a < b) {
				a+=m;
			}else {
				b+=n;
			}
			if(a == b) return a;
			now = Math.min(a, b);
		}
		return -1;
	}

 

 

이제 정확한 답을 내는지 확인해보면 생각한대로 답을 내는것을 확인할수 있다.

 

 

 

아래는 코드의 전문이다.

 

package boj3;

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

public class Boj6604 {
	
	static int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a%b);
	}
	
	static int getYear(int m, int n, int a, int b) {
		if(a == b) return a;
		int max = (m*n)/gcd(m,n);
		int now = Math.min(a, b);
		while(now <= max) {
			if(a < b) {
				a+=m;
			}else {
				b+=n;
			}
			if(a == b) return a;
			now = Math.min(a, b);
		}
		return -1;
	}

	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int t = Integer.parseInt(in.readLine());
		
		int[] data = new int[4];
		
		while(t-- > 0) {
			st = new StringTokenizer(in.readLine()," ");
			for(int i = 0; i < 4; i++) {
				data[i] = Integer.parseInt(st.nextToken());
			}
			sb.append(getYear(data[0],data[1],data[2],data[3])).append('\n');
		}
		
		in.close();
		
		System.out.print(sb);
	}
	
}