백준 6064번 [카잉 달력](C++) -yes6686- 티스토리

백준 문제 풀이: 6064 [카잉 달력]

---

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

문제 설명:

카잉 달력은 M과 N에 의해 정해지는 주기를 가지며, 특정 해는 x와 y가 주어질 때 이를 만족하는 최소 해를 구하는 프로그램을 작성하세요. 만약 해가 존재하지 않으면 -1을 출력합니다.

입력 조건:

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 ≤ T ≤ 10⁵)
• 다음 T개의 줄에 M, N, x, y가 주어집니다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N)

출력 조건:

• 각 테스트 케이스마다 x와 y를 만족하는 최소 해를 출력합니다. 해가 존재하지 않으면 -1을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    while (T--) {
        int M, N, x, y;
        cin >> M >> N >> x >> y;

        int limit = lcm(M, N); // 주기의 최대 값 계산
        int year = x;

        while (year <= limit) {
            // y를 만족하는지 확인
            if ((year - 1) % N + 1 == y) {
                cout << year << '\n';
                break;
            }
            year += M; // M 주기로 다음 해로 이동
        }

        if (year > limit) {
            cout << -1 << '\n'; // 해를 찾지 못한 경우
        }
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 카잉 달력에서 주어진 조건을 만족하는 해를 찾는 문제를 해결합니다.

• 최대 주기 계산:
  • M과 N의 최소공배수(lcm)를 계산하여 반복의 한계를 설정합니다.
• 해 탐색:
  • 초기 해를 x로 설정하고, M 주기로 이동하면서 y를 만족하는 해를 찾습니다.
  • 해가 존재하지 않으면 -1을 출력합니다.

시간 복잡도 분석:

• 각 테스트 케이스에 대해 최대 반복 횟수는 lcm(M, N) / M입니다.
• 최악의 경우에도 반복 횟수는 약 O(N)입니다.
• 전체 시간 복잡도는 O(T × min(M, N))로 제한 내에서 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
3
10 12 3 9
10 12 7 2
13 11 5 6

출력:
33
-1
83

각 테스트 케이스에 대해 조건을 만족하는 최소 해 또는 -1을 정확히 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!