[Algorithm] Baekjoon 6064번 : 카잉 달력

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

vector<int> results;
 
int gcd(int a, int b)
{
    int maxNum = max(a, b);
    int minNum = min(a, b);
 
    while (maxNum % minNum != 0)
    {
        int temp = maxNum % minNum;
        maxNum = minNum;
        minNum = temp;
    }
 
    return minNum;
}
 
int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}
 
void solve(int m, int n, int x, int y)
{
    int maxCount = lcm(m, n);
    bool check = false;
 
    for (int i = x; i <= maxCount; i += m)
    {
        if (y == i % n)
        {
            check = true;
            results.push_back(i+1);
            break;
        }
    }
    
    if (!check)
    {
        results.push_back(-1);
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 0;
 
    int m, n, x, y;
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> m >> n >> x >> y;
        solve(m, n, --x, --y);
    }
    
    for (int i = 0; i < results.size(); i++)
    {
        cout << results[i] << endl;
    }
 
}

 

이렇게 숫자로 푸는 문제들이 참 쉽지 않은 문제같다. 넥슨코테에서 이런 유형이 좀 나왔던거 같은데...

 

m,n,x,y -> 10,12,3,9     라는 예시가 주어졌을 때(백준 예시다)를 생각해보자.

 

먼저 각 케이스의 최대반복문횟수는 m과 n의 최소공배수이다.

나같은 경우는, 규칙 찾으려고 숫자 다적어놓고 하다보니, 최소공배수차례에서 딱 맞아떨어지고 그 다음부터 다시 1,1부터 시작한다는걸 알아내긴 했다.

이게 어떤것을 의미하냐면, 최소공배수 이전의 숫자 쌍들은 중복되는 쌍이 없다는걸 보장한다.

그렇기 때문에 딱 최소공배수까지만 반복문을 돌리면 된다.

최소공배수까지 반복문 돌렸는데도 못찾으면, 애초에 불가능한 값이기 때문에 -1을 리턴해주면 된다.

 

 

먼저 기준을 잡아준다.

우리는 3,9라는 값을 알아야 한다. 그렇다면 x인 3을 기준으로 m만큼(10) 더해준다고 가정해보자.

x를 기준으로 m만큼 카운팅하기 때문에 x는 초깃값 잡아준거 계속 그대로이고, y는 카운팅값 % n을 해준 값이다.

그렇기 때문에 반복문을 통해 y == 카운팅값 % n 일 때의 i가 정답이다.

실제로 우리가 찾아야하는 3,9일때의 카운팅값을 직접 계산해 보면 된다. y값을 n으로 나누기 이전의 값으로 표현하면

3,3   3,13   3,23   3,33   이 될것이고 (m만큼 더해준거임), 여기 y값들을 n으로 나머지연산을 시행한걸로 다시 표현하면

 

3,3(3 % 12),    3,1(13 % 12),   3,11(23 % 12),   3,9(33 % 12)  <--- 이렇게 나오게 된다. 

 

그래서 i가 33일때 y값과 나머지연산한 값이 같으니, 그때의 i값을 리턴하면 된다는 것.

 

다만, 여기서 조심해야 할 점 딱 한가지가 있다.

똑같이 m,n은 10,12 이고 x,y는 2,12라고 가정했을 때 카운팅값을 구해야한다고 생각해보자.

답은 12이다. 근데 위의 로직대로 해버렸을 경우를 생각하자.

 

위 로직대로라면, i가 12일 때, i % m 값이 y랑 같아야 한다.

근데 i는 12, m도 12니까 i % m == 0이라는 결과가 나와서 컴퓨터는 정답이라고 생각 안하고 그냥 넘겨버린다.

이런 비슷한 문제를 다른 문제 풀때도 겪었던 것 같긴 하다.

 

어쨋든 수의 표현을 1~m으로 해서 생긴 문제이기 때문에, 0~m-1로 하면 위의 문제를 해결할 수 있다.

그렇기 때문에 위의 코드에서 x,y를 각각 -1씩 해서 solve에 넘긴것이고, -1한상태에서 답을 구했기 때문에

마지막에 값을 리턴할때는 다시 +1을 해주면 된다.