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

 

 

A년도를 카잉 달력으로 표현하였을 때, <x, y>가 된다고 하면, <x, y>가 주어졌을 때 A가 몇인지 구하는 문제이다.

 

카잉 달력은 <x, y>의 형식으로 표현이 되며, x와 y에는 최대값이 정해져있다. 현실에서도 12월이 지나면 1월이 되듯이, x와 y도 일정 숫자(M, N)를 지나면 1로 돌아간다.

 

예를 들어, M이 10, N이 11이라고 해보자.

 

1년도 -> <1, 1> 

2년도 -> <2, 2>

.

.

.

10년도 -> <10, 10> 이 될 것이다.

 

다음 11년도는 <11, 11>이 될 것 같지만, x(11)가 M(10)을 초과하였으므로, 1로 돌아간다.

그러므로 11년도는 <1, 11> 이 된다.

 

동일한 규칙으로 12년도는 <2, 1>이 된다.

 

이 규칙을 역산하여, <x, y>가 주어졌을 때, 현재 몇년도인지 구하면 되는 문제이다.

 

문제 풀이

 

간단하다. 현재 연도를 A라고 했을 때, A % M = x, A % N = y 가 될 것이다.

(주의할 점은 x와 y의 범위가 0이 아닌 1부터 시작하기 때문에 A % M 이 0이라면, x는 M이고, A % N 이 0이라면, y는 N이다.)

 

이렇게 구한 x, y가 입력으로 주어진 x, y와 동일해지는 A를 구하면 된다.

 

하지만, 이 것을 구하기 위해 A를 무작정 1부터 탐색하게 되면 시간초과가 발생하게 된다.

왜냐하면, M,N의 최대값은 40000이기 때문에, 최악의 경우엔 1600000000 가량의 반복문을 실행해야 하기 때문이다.

 

이를 막기 위해, 본인은 2가지 방법을 사용하였다.

 

1. 반복문의 최대 횟수를 M과 N의 최소공배수로 한다.

 

이 문제에선 x,y가 올바른 년도가 아닌 경우도 존재한다. 이 경우를 바로 캐치하여 반복문을 종료하지 못하면 무한루프가 발생한다. 그러므로, 반복문은 M과 N의 최소공배수만큼만 돌도록 하였고, 마지막까지 조건을 만족하는 A를 발견하지 못하면, -1을 출력하도록 하였다.

 

M와 N의 최소공배수로 한 이유는, x와 y가 M과 N의 나머지로 정해지기 때문이다. <x, y>가 <M, N>이 되는 년도가 마지막 년도이다. 해당하는 카잉 달력의 연도를 A라고 한다면, A % M = 0이고, A % N 도 0일 것이다. 이를 만족하는 숫자는 M과 N의 최소공배수이다.

 

2. A를 1씩 증가하며 탐색하지 않고, M씩 증가시키며 탐색한다.

 

기본적으로, 문제의 조건에 맞는 년도를 찾기 위한 조건은 A % M == x  , A % N == y 두 조건문을 만족하는 것이다.

(물론 A % M이 0일 땐 M으로 바꿔주어야 하고, A  % N 이 0일 땐 N으로 바꿔주어야 한다.)

 

두 조건을 모두 만족하는 경우를 찾는 것이기 때문에, 한가지 경우를 무조건 만족하는 숫자를 기준으로 탐색할 수 있다면 더욱 빠를 것이다.

 

최초에 A를 입력받은 x로 초기화해주자.

그 이후, A에 1씩 더해가며 탐색하는 것이 아니라 A에 M씩 더해가며 탐색하게 되면, A % M 이 x인 숫자를 대상으로만 탐색하게 된다. (M이 아닌 숫자를 더하게 되면 어차피 A % M == x 를 만족하지 않으므로 스킵해도 된다.)

 

M이 40000인 경우, 한 번에 4만씩 넘어가며 탐색을 하기 때문에 최악의 경우에도 4만 번만 탐색하면 된다.

 

이 규칙을 토대로 반복문을 돌며 답을 탐색하면 된다.

 

풀이 코드

int NumCase = 0;
std::cin >> NumCase;

std::vector<int> Answer(NumCase);

 

먼저, 케이스의 수를 입력받고 답을 저장할 Answer 벡터를 선언해주자.

int M = 0;
int N = 0;
int X = 0;
int Y = 0;

std::cin >> M >> N >> X >> Y;

int MaxYears = GetLCM(M, N);

int CurYears = X;

while (CurYears <= MaxYears)
{
    int RemainX = CurYears % M;
    int RemainY = CurYears % N;

    if (RemainX == 0)
    {
        RemainX = M;
    }

    if (RemainY == 0)
    {
        RemainY = N;
    }

    if (RemainX == X && RemainY == Y)
    {
        break;
    }

    CurYears += M;
}

if (CurYears <= MaxYears)
{
    Answer[i] = CurYears;
}
else
{
    Answer[i] = -1;
}

 

위 코드는 각 케이스에 대한 반복문 내부 코드이다.

 

먼저, M, N, X, Y를 입력받아 준다.

이후 M과 N의 최소공배수를 구해, 반복문의 종료 조건을 설정해준다.

 

CurYears는 최초에 X로 초기화해주고, M씩 더해가며 탐색할 것이다.

 

내부에선 CurYear를 M과 N으로 나눈 나머지를 구해주고 있다. 그리고 만약 나머지가 0이라면, 해당 값을 M과 N으로 대체해주고 있다.

 

나머지가 X, Y와 같다면 반복문을 종료하고 Answer에 답을 삽입해주었다.

 

만약 반복문을 나간 이후, CurYears가 MaxYears보다 크다면, 답을 찾지 못하고 반복문을 종료한 것이기 때문에 이 경우엔 -1을 삽입해주었다.

 

for (int i = 0; i < Answer.size(); i++)
{
    std::cout << Answer[i] << "\n";
}

 

마지막엔 답을 출력해주면 된다.

 

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int GetGCD(int _A, int _B)
{
    int Remain = 0;

    while (_B > 0)
    {
        Remain = _A % _B;
        _A = _B;
        _B = Remain;
    }

    return _A;
}

int GetLCM(int _A, int _B)
{
    int LCM = _A * _B / GetGCD(_A, _B);

    return LCM;
}

int main()
{
    Init();

    int NumCase = 0;
    std::cin >> NumCase;

    std::vector<int> Answer(NumCase);

    for (int i = 0; i < NumCase; i++)
    {
        int M = 0;
        int N = 0;
        int X = 0;
        int Y = 0;

        std::cin >> M >> N >> X >> Y;

        int MaxYears = GetLCM(M, N);

        int CurYears = X;

        while (CurYears <= MaxYears)
        {
            int RemainX = CurYears % M;
            int RemainY = CurYears % N;

            if (RemainX == 0)
            {
                RemainX = M;
            }

            if (RemainY == 0)
            {
                RemainY = N;
            }

            if (RemainX == X && RemainY == Y)
            {
                break;
            }

            CurYears += M;
        }

        if (CurYears <= MaxYears)
        {
            Answer[i] = CurYears;
        }
        else
        {
            Answer[i] = -1;
        }
    }

    for (int i = 0; i < Answer.size(); i++)
    {
        std::cout << Answer[i] << "\n";
    }

    return 0;
}