백준 6064 카잉 달력 [자바]

in Develop / Solving

baekjoon 6064 카잉 달력

java

문제 분석

  • 신기한 달력
  • x, y 두 개의 수로 연도를 계산하고, <1, 1> 이 1 <2, 2> 이 2 <3, 3> 이 3
  • 이렇게 하나씩 올라가다가, x > M, y > N 이면 1로 초기화
    • ex) M = 10, N = 12일 때 <11, 11>은 <1, 11>이 됨(11년)
  • 만약 <x, y> == <M, N>이면, 멸망해버림
  • 주어지는 조건에 대해 몇번째 해인지 구하고, 있을 수 없는 해면 -1 출력.

입력조건

int_T(테스트케이스 수)
int_M N x y

풀이과정

  • 두 수의 최소공배수인 해에서 멸망함
  • x < y이면, x에 M을 더하고, y > x이면, y에 N을 더한다.
  • 저러다가 x == y가 되면, 그 때의 해가 답이 됨.
  • 만약 올라가다가 (x or y) > MN의 최소공배수 보다 커지면 -1 출력

코드 구성

  1. 입력받기

  2. 최소공배수 구하기

    • 유클리드 호제법 이용 최대공약수 구하는 코드

      private static int getgcd(int x, int y) {
    if(x % y == 0) return y;
    return getgcd(y, x%y);
}

  3. 연도 연산 실행

    while(x <= finalyear && y <= finalyear) {
    if(x == y) {
        sb.append(x + "\n");
        continue test;
    }
    else {
        if(x < y) x += N;
        else	  y += M;
    }
}

전체 코드

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

public class BJ6064_카잉달력 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		test: for(int i = 1; i <= T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			// 유클리드 호제법 이용 최소공배수 계산.
			int GCD = getgcd(N, M);
			int finalyear = N*M/GCD;
			
			// gcd를 넘어가면 멸망
			while(x <= finalyear && y <= finalyear) {
				if(x == y) {
					sb.append(x + "\n");
					continue test;
				}
				else {
					if(x < y) x += N;
					else	  y += M;
				}
			}
			
			sb.append("-1\n");
		}
		System.out.println(sb);
	}

	private static int getgcd(int x, int y) {
		if(x % y == 0) return y;
		return getgcd(y, x%y);
	}
}