[백준] 6064번 카잉 달력 : C++ / 파이썬(python) 설명

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

6064번: 카잉 달력

 

 

---

 

 

Hint

 

M,N,x,y가 10 12 3 1로 주어졌다고 가정할 때

10A + 3 = 12B + 1을 만족하는

<A,B>를 구해야 합니다.

이를 구하는 방법으로 유클리드 확장법 등의 수학적인 스킬이 존재합니다

(하지만 이 글의 솔루션에서는 사용하지 않습니다)

 

<0:0>  3>1 이므로 b += 1

<0:1>  3<13 이므로 a += 1

<1:1> 13=13이므로 만족

 

C++ 구문에서는 위 방식을 사용했습니다

 

 

---

Solution

 

 

C++ 구문은 위의 Hint에서 언급한 것과 같이

좌항과 우항의 크기 비교를 통해

A,B를 하나씩 추가하는 방식을 했으며

O(N)의 시간 복잡도를 가집니다

#include <iostream>
using namespace std;

int kaing(int, int, int, int);

int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{

		int M, N, x, y;
		cin >> M >> N >> x >> y;
		kaing(M, N, x, y);


	}

	return 0;
}

int kaing(int M, int N, int x, int y)
{
	int a, b;
	a = 0, b = 0;
	int a2, b2;

	while (true)
	{
		a2 = a * M + x;
		b2 = b * N + y;
		if (a2 == b2)
		{
			cout << a2 << "\n";
			return 0;
		}

		else if (a2 > b2)
			b += 1;

		else
		{
			a += 1;
			if (a * M + x > M * N)
			{
				cout << -1 << "\n";
				return -1;
			}
		}
	}
}

해당 구문을 python으로 변환하면 시간 초과가 발생하고 PyPy로 실행 시 통과됩니다

 

그래서 Python으로 돌아가는 알고리즘은

최대 공약수를 이용했습니다.

 

import sys
import math


def z(x, max_k):
    while x <= max_k:
        if x % n == y % n:
            return x
        x += m
    return -1


input = sys.stdin.readline

for i in range(int(input())):
    m, n, x, y = map(int, input().split())
    max_k = m * n // math.gcd(m, n)
    
    if y > x:
        m, n = n, m
        x, y = y, x
        
    print(z(x, max_k))