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

---

처음에는 1,1부터 각 1씩 증가시키면서 하는 방식^[각주:1]으로 풀려고 했다.

#include<stdio.h>
int main() {
	int T;
	int M, N, x, y;
	int i, j, cnt;

	scanf("%d", &T);
	while (T--) {
		i = 1, j = 1, cnt = 1;
		scanf("%d %d %d %d", &M, &N, &x, &y);
		while (1) {
			if (x == i && y == j) {
				printf("%d\n", cnt);
				break;
			}
			i++, j++, cnt++;
			if (i > M)
				i = 1;
			if (j > N)
				j = 1;
			if (i >= M && j >= N) {
				printf("-1\n");
				break;
			}
		}
	}
}

그랬더니 시간 초과가 떴다. 아무래도 40,000, 40,000까지 다 돌리기에는 무리였나보다.

그래서 고민 끝에 다른 방법으로 한 쪽을 기준으로 삼고 돌리기로 했다.

방법은 다음과 같다.

M과 N중 더 작은 쪽을 기준으로 삼는다. SWAP을 이용해서 N이 더 작도록 바꿔준다.

입력받은 x값을 기준으로 삼고 y값만 바꿔주면서 비교한다.

물론 이 때 y값을 _y에 저장해주어야 한다.

M-N만큼 _y에 더해주되 _y가 N보다 큰 경우에는 N만큼 감소시켜준다.

단, 초기값이 엄청나게 차이날 경우를 대비해서 무한루프를 돌렸다.

cnt는 초기값을 x로 주고 1바퀴당 M씩 증가했다.

끝까지 다 돌았음에도 불구하고 같은 값이 나오지 않는다면 유효하지 않은 표현이므로 -1을 출력한다.

소스는 다음과 같다.

#include<stdio.h>
#define SWAP(i,j) {int tmp; tmp=i; i=j; j=tmp;}
#define FOR(i,j) for(int i=0;i<j;i++)
int main() {
	int T;
	int M, N, x, y;
	int cnt, _y;

	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &M, &N, &x, &y);
		if (N > M) {
			SWAP(M, N);
			SWAP(x, y);
		}
		cnt = x;
		_y = x;
		FOR(i, N) {
			for (;;) {
				if (_y > N)
					_y -= N;
				else
					break;
			}
			if (_y == y) {
				printf("%d\n", cnt);
				break;
			}
			_y += (M - N);
			cnt += M;
			if (i == N-1)
				printf("-1\n");
		}
	}
	return 0;
}

1. 브루트포스 [본문으로]