백준 6064 카잉 달력 (c++) : 피너클

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

6064번: 카잉 달력

수학문제다.

만약 <M:N>이 <2:3>이라면 

<1:1> -> <2:2> -> <1:3> -> <2:1> 이런 식으로 날짜가 진행된다.

int test;
cin >> test;
while (test-- > 0) {
	int m, n, x, y;
	cin >> m >> n >> x >> y;

while반복문으로 모든 케이스를 확인한다.

값들을 입력받는다.

	int k = 1;
	int a = 1, b = 1;

k는 몇 번째 인지, a는 월, b는 일 을 나타낸다.

우리는 1:1에서 x:y까지 얼마나 걸리는지를 구해야한다.

모든 값을 확인하기에는 시간이 부족할 것 같다. 그렇기에 월 값을 고정시킬것이다.

문제의 예시중 하나인 [10 12 3 9] 를 보자.

1:1에서 3:9까지 얼마나 걸리는지느 바로 몰라도 1에서 3까지는 알수있다.

	k += x - a;
	b += x - a;
	while(b > n) b -= n;
	a = x;

k에 x - a만큼을 더해준다. a에서 x까지 가는데 걸리는 비용이다.

b에서 x-a만큼 더해주고 만약 b가 N보다 커졌다면 N을 빼준다. 그후 a를 x로 바꿔준다.

이제 1:1에서 3:3까지는 갔다. 이제부터 <월:일>에서 월은 절대로 변하게 하지 않을것이다.

	if (a == x && b == y) {
		cout << k << endl;
	}

만약 a == x고 b == y라면 바로 k를 출력해준다.

	else {
		memset(visited, false, sizeof(visited));
		visited[b] = true;
		bool chk = false;

아니라면 visited를 초기화 하고 현재 b를 true로 바꾼뒤 chk를 만는다. chk가 true라면 x:y에는 갈수 없다는 뜻이다.

		while (1) {
			k += m;
			b += m;
			while (b > n) b -= n;

이제 k와 b에 m을 더해준다. 3:3에 10을 더하면 3:1이 될것이고 다시 10을 더하면 3:11이 될것이다.

'월'은 절대 바뀌지 않고 '일'만 바뀐다. 만약 b가 n보다 크다면 n을 빼준다.

			if (visited[b]) {
				chk = true;
				break;
			}

만약 이전에 방문한적이 있는 '일' 이라면 앞으로도 계속해서 방문한 적이 있는 '일'만 방문할것이다.

무한 루프에 빠지기 전에 chk를 true로 바꾸고 반복문에서 나온다.

			if (a == x && b == y) {
				cout << k << endl;
				break;
			}
			visited[b] = true;

만약 목적에 도달했다면 k를 출력하고 반복문에서 나온다.

아니면 visited[b]를 true로 바꾼다.

			}
		if (chk) cout << -1 << endl;

while문에서 나왔는데 chk가 true라면 -1을 출력하면 된다.

#include <iostream>
#include <cstring>

using namespace std;

bool visited[400001];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int test;
	cin >> test;
	while (test-- > 0) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;

		int k = 1;
		int a = 1, b = 1;

		k += x - a;
		b += x - a;
		while(b > n) b -= n;
		a = x;
		if (a == x && b == y) {
			cout << k << endl;
		}
		else {
			memset(visited, false, sizeof(visited));
			visited[b] = true;
			bool chk = false;
			while (1) {
				k += m;
				b += m;
				while (b > n) b -= n;
				if (visited[b]) {
					chk = true;
					break;
				}
				if (a == x && b == y) {
					cout << k << endl;
					break;
				}
				visited[b] = true;
			}
			if (chk) cout << -1 << endl;
		}
	}
}

전체코드다.