백준 6064 - 카잉 달력(C++)

문제 링크입니다. https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

수학적 규칙을 찾아 푸는 문제였습니다.

문제 조건

출력 예시

 

<1 : 1> 부터 <M : N>까지 달력이 증가할 때, <X : Y>는 몇 번째 해인지를 구하는 문제입니다.

먼저 달력이 어떻게 증가하는지 확인하겠습니다.

 

규칙을 찾기 위해서 카잉 달력을 끝까지 확인해보겠습니다.

<X : Y> 로 이루어진 카잉 달력을 X값의 변화에 따라 나열해봤습니다.

이때 X 값이 같을 때 Y값 변화를 확인해보겠습니다.

M = 10, N = 12 인 경우, X값이 5일때 Y값은 5 -> 3 -> 1 -> 11 -> 9 - >7 로 변합니다

값이 변화하는 규칙을 찾아보면

(5 = X) ->(5 + M) % N -> (3 + M) % N -> (1 + M) % N -> (11 + M) % N -> (9 + M) % N 의 값으로 변합니다. 

 

해당 규칙이 맞는지 다른 X값으로 확인해봤을때, 값이 정확함을 확인할 수 있음으로 해당 규칙으로 변함을 알 수 있습니다.

 

따라서 <X : Y> 좌표가 있는지를 확인하려면, <X : X>에서 시작하여, (K + M) % N 로 값을 계속 바꾸면서 Y와 같아지는 경우가 생기는지 확인하면 됩니다.

<X : Y>가 존재하지 않는 경우도 있습니다.

이때는 2가지 경우가 있습니다.

1. <X : X> 에서 시작해서 <X : X>로 돌아왔을 경우

2. <X : K>의 해가 M*N을 넘어갔을 때

이 경우 -1를 출력하면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <deque>
#include <stack>

using namespace std;

int M, N, X, Y;
int test_case;
int cnt;

bool solve() {
	int start = X % N;
	if (start == 0) start = N;
	while (1) {
		if (cnt * M + X > M * N) return false;  
		if (start == Y) return true;
		start = (start + M) % N;
		if (start == 0) start = N;
		if (start == X) return false;
		cnt++;
	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int i = 1; i <= test_case; i++) {
		cin >> M >> N >> X >> Y;
		if (solve()) {
			cout << X + cnt * M << "\n";
		}
		else {
			cout << "-1" << "\n";
		}
		cnt = 0;
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요