#6064: 카잉 달력

백준 6064번: 카잉 달력

문제:

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력:

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 은 카잉 달력의 마지막 해를 나타낸다.

풀이:

• 처음에 이 문제를 풀 때 #1476: 날짜 계산 문제처럼 모든 년도를 0부터 1씩 올리면서 구하는 방식으로 풀려고 하였으나 시간 초과가 나서 다른 방식을 찾아보다가 방앗간 개발자님의 블로그 포스팅을 접하게 되었다.
• 방앗간 개발자님의 블로그 포스팅님의 풀이법은 이러하다. 우선 범위를 넘어 답이 없을 경우에는 -1을 출력해야 되기 때문에 범위가 어디까지인지 고려해야 된다. 최대 범위는 M, N의 최소공배수이다. 왜냐하면 인 경우에는 문제를 봐서 알겠지만 최소공배수가 마지막 해를 나타내기 때문이다. 따라서 최소공배수를 구하기 위하여 유클리드 호제법을 이용하여 최대공약수를 구한 뒤 최소공배수와의 관계식을 이용하여 최소공배수를 구해주는 함수 lcm을 만들어 준다.
• 이제 문제의 핵심 풀이법을 설명하겠다. 우선, x는 해를 M으로 나누었을 때의 나머지이다. 따라서 우리는 모든 년도를 고려하지 않고 x에 M을 더해준 해만 고려하면 된다. 따라서 for문을 이용하여 x을 M만큼 올려주면서 거꾸로 N으로 나누어 나머지를 구하였을 때 y가 되는 경우에는 답을 찾은 것이므로 현재 x값을 출력한 뒤 for문을 나간다. 만약에 for문이 끝날 때까지 출력이 안되고 x가 최대값보다 크면 -1을 출력한다.

코드:

#include <iostream>

using namespace std;

int lcm(int a, int b){
	//큰 수 항상 a로 오도록하기
	int lcm, original_a = a, original_b = b;
	if(a<b){
		int temp = a;
		a = b;
		b = temp;
	}
	//최대공약수 구하기
	while(a%b!=0){
		int temp = a;
		a = b;
		b = temp%b;
	}
	//최소공배수 구하기
  lcm = original_a*original_b/b;
	return lcm;
}

int main(){
	int num_years, M, N, x, y;
	//입력
	cin >> num_years;
	for(int i = 0; i < num_years; i++){
		cin >> M >> N >> x >> y;
		//종말의 해를 구하기 위해 M, N의 최소공배수 계산
		int max = lcm(M, N); 
		//x를 M만큼 더하여 가능한 모든 경우 x가 나올 수 있는 모든 경우의 수 고려
		for(x; x<=max; x+=M){
			//x가 현재 구하는 년도라고 생각하면 편하다
			//N만큼 나누어 떨어지면 y = N이 가능하므로 N으로 y와 비교 아닐경우 나머지를 y와 비교
			if(((x%N==0) ? N : x%N)==y){ 
				cout<<x<<'\n';
				break;
			} 
		}
		//구한 년도가 범위 밖일 경우 -1 출력
		if(x>max) cout<< -1 <<'\n';
	}
}