6064 카잉달력

www.acmicpc.net/problem/6064

6064번: 카잉 달력

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int M, N;//x와 y의 최대 범위
int x, y;//날짜
int cx, cy;//계산하는 날짜
int num[40001];//날짜 체크하는 함수
int Time = 0;//날짜 결과값
void init() {//초기화 및 초기 입력
	M = N = 0;
	cx = cy = Time=0;
	memset(num, 0, sizeof(num));
	scanf("%d %d %d %d", &M, &N,&x,&y);
}
void kCal() {//카잉 달력 계산 
	int flag = 0;
	while (1) {
		cx++; cy++; Time++;
		if (cx == x && cy == y) {//결과값이면 종료
			break;
		}
		if (cx == M + 1)cx = 1;
		if (cy == N + 1)cy = 1;
		if (cx == x && cy == y) {//결과값 찾음
			flag = 1; break;
		}
		while (cx==x) {//y값 계산
			cy += M;
			cy = cy % N;
			if (cy == 0)cy = N;
			Time += M;
			if (cx == x && cy == y) {//결과값 찾음
				flag = 1; break;
			}
			if (num[cy] == 0) {
				num[cy] = 1;
			}
			else {//결과값이 없다면 -1 종료
				flag = 1;
				Time = -1;
				break;
			}
		}
		if(flag)break;
	}
}
int main(void) {
	int testCase = 1;
	scanf("%d", &testCase);
	for (int tc = 1; tc <= testCase; tc++) {
		init();
		kCal();
		cout << Time << endl;
	}
	return 0;
}

하드코딩을 한 것 같긴합니다.

 

여기서 포인트는 x를 찾고 y값을 (y+M)%N을 해주는것?

 

이것이 시간초과를 줄일 수 있는 포인트이고,

 

이문제를 다풀고 다른 사람들 풀이 보니 최대공배수를 이용해서 최소공배수 넘으면 예외를 시키는 경우한것 같은데

그렇게 하기보다는

 

배열 하나에 y의 나머지 값을 저장을 저장 시켜서 저장한 값이 다시 나오면 그경우는 해를 못찾았다고 판단하여

문제를 해결 했습니다. 

 

좀더 직관적이고 나머지수가 반복되는 것을 캐치 했다면 오히려 빠르게 문제 풀이에 적용할 수 있지 않을까

생각합니다.