BOJ | 6064 카잉달력

Link

BOJ 6064

Problem

최근에 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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

문제로만 보면 잘 이해가 가지 않는다.
고로, M=3, N=4로 예시를 들어보았다.

1번째 해: <1,1>
2번째 해: <2,2>
3번째 해: <3,3>
4번째 해: <1,4>
5번째 해: <2,1>
6번째 해: <3,2>
7번째 해: <1,3>
8번째 해: <2,4>
9번째 해: <3,1>
10번째 해: <1,2>
11번째 해: <2,3>
12번째 해: <3,4>

이렇게 x=M, y=N일 시인 마지막 해는 12번째 해이다.
(M과 N의 최소공배수)

여기서 <2,1>이 몇번째 해인지 찾는다고 하자
x=2이니 2번째 해일 가능성이 있다.
다음으로 x=2인 구간은 5번째, 8번째, 11번째이다.
이처럼 M만큼 건너뛰면서 x가 동일한 구간을 확인할 수 있다.

여기서 순서(i)를 N으로 나눈 값이 y를 N으로 나눈 값과 같다면 해당 해가 구하는 답이다.
> 사실 처음에는 i%N==y면 되지 않을까, 했는데 i%N이 0이고 y가 N인 경우가 있기에 i%N==y%N으로 처리했다.

따라서 코드로 작성하면

for (int i=x; i<=M*N; i+=N)
	if(i%N==y)
		return i;

가 된다.

찾지 못하면 -1을 출력하도록 처리해준다.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int func(int M, int N, int x, int y)
{
	for (int i = x; i <= M*N; i += M)
	{
		if (i % N == y%N)
			return i;
	}
	return -1;
}

int main() {
	int tc;
	scanf("%d", &tc);

	while (tc--)
	{
		int M, N, x, y;
		scanf("%d %d %d %d", &M, &N, &x, &y);

		printf("%d\n", func(M, N, x, y));
	}

	return 0;
}

cin, cout 시간초과 처리해주기 귀찮아서 그냥 scanf, prinf로 작성했다.

Result