알고리즘 :: 백준 :: Bruteforce :: 6064 :: 카잉 달력

문제

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

문제접근

• https://velog.io/@embeddedjune/알고리즘-백준-Bruteforce-1476-날짜-계산 문제와 굉장히 유사한 문제다. 차이점이 있다면 각 변수에 대한 상한값도 입력을 받는다는 점이다.
• 이 문제는 1476-날짜계산문제와 동일한 알고리즘으로 풀 수 있다.
  • while(true)문으로 M과 N에 대한 입력받은 상한값까지 값을 증가시켜가면서 우리가 찾으려는 연도를 찾을 수 있다.
  • 그러나 이 문제에서는 그렇게 풀면 안된다!
  • M과 N의 상한값이 40,000이고, 최악의 경우에는 $40,000 \times 40,0000 = 16억$번의 연산을 해야하므로 제한시간내에 풀 수 없다.
• 시간내에 풀이하기 위해서는 어떻게 해야할까? 바로 시간초과가 나는 이유는 바로 높은 상한값을 가진 변수가 두 개이기 때문이다.
• 즉, 변수 하나를 고정한다면 다른 변수에 대해서만 고려해주면 되기 때문에 상한이 16억에서 4만으로 줄어든다!

상한이 M=10, N=12이고 <3:9>가 몇 년도인지 찾는 경우를 생각해보자.

• 우선 x = 3인 경우로 변수 하나를 고정하자. 처음으로 x = 3인 경우는 3번째 연도인 <3 : 3>이다. 그 뒤 10년이 흐르면 <3 : 1>년이다. 그 뒤 또 10년이 흐르면 <3 : 11> 이다.
• 결국, M의 상한선마다 x는 그대로고 y만 바뀌므로 우리는 M씩 증가시키면서 y를 검사해주면 된다.
• 그리고 나눗셈을 사용해야하므로 1476-날짜계산 문제에서 사용했던 전략을 그대로 사용한다. ((임의의 값 - 1) % (상한값)) + 1 전략을 이용한다.

코드

#include <iostream>
using namespace std;

int T, M, N, x, y;

int main( ) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> T;
	while (T--) {
		cin >> M >> N >> x >> y;
		bool flag = false;
		for (int i = x; i < M * N; i += M)	// x에 대해 M씩 증가하면서 찾는다.
			if (((i - 1) % N) + 1 == y) {	// 우리가 찾던 y값이라면, 반환
				cout << i << '\n';
				flag = true;
				break;
			}
		if (!flag) cout << -1 << '\n';
	}
}

결과