[백준 / C++] 카잉 달력 (실버1, 6064)

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

문제

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

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

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

입력

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

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

예제 입력 1

3
10 12 3 9
10 12 7 2
13 11 5 6

예제 출력 1

33
-1
83

---

문제 풀이

이번 문제는 카잉 달력의 범위 N과 M이 주어졌을 때 <x:y> 년도가 몇 번째 해를 나타내는지 구해야 하는 문제입니다.

 

예를 들어 N = 2, M = 3이라면 다음과 같이 달력을 완성할 수 있습니다.

1 : 1 , 1

2 : 2 , 2

3 : 1 , 3

4 : 2 , 1

5 : 1 , 2

6 : 2 , 3

 

즉, N과 M의 최소 공배수까지 표현이 가능하며, 이를 넘어가는 날짜는 표현이 불가능한 것을 확인할 수 있습니다.

여기서 최소 공배수는 다음과 같은 공식으로 구할 수 있습니다.

 

N * M / (N, M의 최대 공약수)

위 공식을 통해 최소 공배수를 구하는 로직을 구현한다면 다음과 같습니다.

// 최대 공약수 구하기
int res = 0;
int a = m;
int b = n;
while (b != 0)
{
	res = a % b;
	a = b;
	b = res;
}

// 최소 공배수 구하기
int mx = (m * n) / a;

 

다음으로는 현재 날짜를 체크하는 방법입니다.

저는 위와 같이 M = 2, N = 3 인 경우 1, 2 를 날짜로 변환하기 위해 idx를 설정하여 계산을 진행하였습니다.

 

N이 더 크므로 y값을 기준으로 ((y + (n * idx)) % m == x % m) 조건이 성공한다면 1, 2가 구해지는 idx이므로 (n * idx) + y를 반환해주고, M이 더 크다면 반대로 x값을 기준으로 체크해주었습니다.

// n이 큰 경우
while (true)
{
	if ((idx * n) + y > mx)
	{
		cout << -1 << endl;
		break;
	}


	if ((y + (n * idx)) % m == x % m)
	{
		cout << (n * idx) + y << endl;
		break;
	}
	else
	{
		idx++;
	}
}

여기서 (n * idx) + y의 값이 위에서 구한 최소 공배수를 넘어선다면 달력에 표현 불가능한 날짜이므로 -1을 반환하는 방식으로 문제를 해결하였습니다.

코드

#include <iostream>
using namespace std;

int n;

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int x, y, n, m;
		cin >> m >> n >> x >> y;

		// 최대 공약수 구하기
		int res = 0;
		int a = m;
		int b = n;
		while (b != 0)
		{
			res = a % b;
			a = b;
			b = res;
		}

		// 최소 공배수 구하기
		int mx = (m * n) / a;

		// x + (m * ? ) % m == y;
		// -> ? + x가 정답
		int idx = 0;

		if (x > y)
		{
			while (true)
			{
				if ((idx * m) + x > mx)
				{
					cout << -1 << endl;
					break;
				}


				if ((x + (m * idx)) % n == y % n)
				{
					cout << (m * idx) + x << endl;
					break;
				}
				else
				{
					idx++;
				}
			}
		}
		else
		{
			while (true)
			{
				if ((idx * n) + y > mx)
				{
					cout << -1 << endl;
					break;
				}


				if ((y + (n * idx)) % m == x % m)
				{
					cout << (n * idx) + y << endl;
					break;
				}
				else
				{
					idx++;
				}
			}
		}
	}
}