6064: 카잉 달력

6064번: 카잉 달력

풀이

#idea

• 마지막 해는 M과 N의 최소공배수다.
• 현재 해를 K라고 할 때, K = M * a + x = N * b + y 부정방정식의 최소 해

 

#구현 방안

• M과 N의 최소공배수 구하기
  • 1~200까지의 소수 데이터를 만들어놓고 공통인수 찾기
  • 두 수 중 작은 수를 n배 하며 같은 수가 나올 때까지 반복하기
• 부정방정식의 최소 해 구하기
  • 초기 값 지정 a, b = 0
  • M * a + x 와 N * b + y 중 작은 쪽부터 a나 b를 1씩 증가시키기
  • M * a + x 와 N * b + y 가 같아지면 멈추기
  • 둘 중 하나가 최소공배수를 넘었다면 해가 없으므로 -1 출력하기

 

#source code

using System;

class program
{
    static int T, M, N, x, y, L;

    static void Main()
    {
        T = int.Parse(Console.ReadLine());
        for(int i = 0; i < T; i++)
        {
            string[] testcase = Console.ReadLine().Split();
            M = int.Parse(testcase[0]);
            N = int.Parse(testcase[1]);
            x = int.Parse(testcase[2]);
            y = int.Parse(testcase[3]);
            
            L = Least(M, N);

            int a = 0; int b = 0;
            int X = x; int Y = y;

            // 부정방정식 해 찾기
            while (M * a + x != N * b + y)
            {
                if (M * a + x > N * b + y) b++;
                else a++;
                if (M * a + x > L || N * b + y > L) break;
            }
            if (M * a + x == N * b + y) Console.WriteLine(M * a + x);
            else Console.WriteLine(-1);
        }
    }

    static int Least(int x, int y)  // 최소공배수 구하기
    {
        int a = x; int b = y;
        while(a != b)
        {
            if (a > b) b += y;
            else a += x;
        }
        return a;
    }
}

비효율적인 코드이긴 한데 한방에 딱 떠오른 알고리즘은 이거였다.

최소공배수를 구하는 것보단 최대공약수를 구하는 것이 훨씬 더 간단하다.

M * a + x 같은 수식은 반복해서 사용할 거면 차라리 한 번 연산하고 변수 하나 지정해서 저장하는 편이 메모리 관리에 좋지 않을까...