백준 6064. 카잉 달력

알고리즘 기초 문제 중 브루트포스 기초 문제(500)

카잉 달력

1. 간단 설명

문제 설명이 직관적이지 못한데, 번역체라 그런듯

문제 자체는 날짜 계산문제와 같은 맥락이지만

M과 N의 범위가 40000만으로 더 크다

2. 예시

M = 10, N = 12라면
1 = <1:1>
2 = <2:2>
...
9 = <9:9>
10 = <10:10>
11 = <1:11>
12 = <2:12>
13 = <3:1>
14 = <4:2>

이런식으로 계산된다

X = 3, Y = 9일때 는 몇번째 해인지를 구하는 문제

3. 알고리즘

M과 N이 작다면 직접 계산하는것으로도 가능하다

예를 들어 M, N, X, Y가 10, 12, 3, 9 라면

1년부터 직접 세면서 해당 X,Y값이 나올때 까지 계산해도 된다

1. M, N, X, Y 입력받기
2. i를 1부터 16억까지 반복
3. i를 이용해 현재 x, y(cur_x, cur_y)를 계산한다
	3-1. cur_x와 curx_y를 1 증가시킨다
	3-2. 만약 M과 N을 넘는다면, 1로 초기화시킨다
	3-3. cur_x, cur_y가 X, Y와 같다면 i를 출력한다

그러나, M, N 의 최대값이 40000이므로, 최대 16억번을 순회해야하므로 시간초과가 발생한다

이를 해결하기 위해서 1씩 증가시키는게 아닌 다른 방법이 필요하다

위의 M, N, X, Y가 10, 12, 3, 9 를 예를 들면

M, N은 10, 12이므로, 이 두 수로 표현할 수 있는 년도의 끝(멸망해)는 60이다

1에서 60사이의 수 중에서, X가 3인 숫자를 먼저 찾아보면

X가 11이 될 때 마다 1로 초기화 되므로, 의심되는 년도들 3, 13, 23, 33, 43, 53이다

이 수들로 Y가 9가 되는 숫자들을 찾아본다

3 -> 3
13 -> 13 % 12 = 1
23 -> 23 % 12 = 11
33 -> 33 % 12 = 9 V
43 -> 43 % 12 = 7
53 -> 53 % 12 = 5

이므로, 33일때, X가 3, Y가 9가 된다

이를 정리하면

1. M, N, X, Y 입력받기
2. i를 X의 예상되는 수들로 지정하고 하나씩 탐색해본다
	2-1. 현재 의심되는 수 i를 N으로 나누어본다
	2-2. 만약 나머지가 0이라면, Y의 마지막 수임을 표시해둔다
		- i가 12이고, Y가 12인경우, i%Y가 0이 되버리는데, 정답 출력을 위해 ny를 12로 저장해둠
		- 0~11년도가 아니라 1부터 시작하기 때문
	2-3. 만약 나머지가 Y라면, 이 수가 해당 년도이므로 이를 출력하고 종료한다

4. 소스코드

#include <iostream>
#include <numeric>

using namespace std;

int solution(int M, int N, int x, int y) {
	int result = -1;
	int max_i = lcm(M, N); // 멸망해
	for (int i = x; i <= max_i; i += M) {
		int ny = i % N;
		if (ny == 0) {
			ny = N;
		}
		if (ny == y) {
			result = i;
			break;
		}
	}

	return result;
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	int T; cin >> T;
	while (T--) {
		int M, N, x, y;
		cin >> M >> N >> x >> y;

		cout << solution(M, N, x, y) << '\n';
	}

	return 0;
}

기존의 날짜 세기에서 약간 응용된 버전의 문제

‘중국인의 나머지 정리’라는 태그가 있던데 이게 어떤걸 의미하는지 추후 학습해봐야겠다