[백준][C#] 6064 카잉 달력 - 실버1

문제 보기

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

6064번: 카잉 달력

 

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

 

 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

 

 

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

 

 

정답 비율이 정말 낮은 문제다.

실버1 문제를 풀다보니 점점 이런 정답률의 문제가 늘어나는 것 같다.

그러나 한 번에 성공하였다.

대신 풀이 방법을 생각하는 데에 2시간은 걸렸다.

다 풀고 다른 사람들은 어떻게 풀었나 찾아보는데

물론 원리야 같지만... 난 정말 이상하게 풀었구나 싶더라 ㅋㅋㅋ

 

 

우선 문제를 풀어보자.

지문이 좀 알기 어렵지만 M = 10, N= 12의 경우 아래와 같은 순서로 해를 나타낸다는 뜻이다.

 

1년 <1:1>

2년 <2:2>

3년 <3:3>

4년 <4:4>

5년 <5:5>

6년 <6:6>

7년 <7:7>

8년 <8:8>

9년 <9:9>

10년 <10:10>

11년 <1:11>

12년 <2:12>

13년 <3:1>

14년 <4:2>

.

.

.

 

한 번 나열해 보았더니 참 알아보기 쉬워졌다.

 

일단 나는 <x:y>가 유효하지 않을 표현일 경우 (-1을 출력하는 경우)를 생각해 보았다.

M = 10, N = 12일 경우를 예로 들고 소인수분해를 해본다.

10 = 2 x 5

12 = 2 x 2 x 3

최대공약수가 2라는 것을 알 수 있다.

이 말은 |x-y|는 항상 2로 나누어 떨어진다는 뜻이다.

 

이 문제를 식으로 나타내보면

k % 10 = x

k % 12 = y 이다.

 

식을 풀어보자.

 

k % 10 = x

k % 12 = y

 

k = x + a x 10

k = y + b x 12

 

x = k - a x 10

y = k - b x 12

(a, b의 의미는, 달력에서 M, N이 몇 번 반복되었는가이다.)

 

x - y =  k - a x 10 - k + b x 12

( y - x로 식을 정리해도 무방하다.)

 

x - y = b x 12 - a x 10

 

x - y = b x 2 x 2 x 3 - a x 2 x 5

 

x - y = 2 x ( b x 2 x 3 - a x 5)

 

즉 a, b가 무엇이든

x - y는 최대 공약수인 2의 배수일 수밖에 없다.

10, 12가 아니더라도 모두 마찬가지다.

 

int gcd = GCD(M, N);
int lcm = LCM(M, N);

if (abs % gcd != 0)
	Console.WriteLine("-1");

 

        private static int GCD(int value1, int value2)
        {
            int smallValue = value1 < value2 ? value1 : value2;
            int maxMeasure = 1;

            for (int i = 2; i <= smallValue; i++)
            {
                if (value1 % i == 0)
                {
                    if (value2 % i == 0)
                    {
                        maxMeasure = i;
                    }
                }
            }

            return maxMeasure;
        }

        private static int LCM(int value1, int value2)
        {
            return (value1 * value2 / GCD(value1, value2));
        }

최대 공약수와 최소 공약수를 구하는 함수인데

자세한 설명은 생략한다...

 

 

이제 마지막으로

그래서 몇 년도인지는 어떻게 구했는가?

// 계산에 이용되는 현재X 현재Y 값이다. 입력으로 들어온 x, y 값을 넣어 초기화.
int curX = x;
int curY = y;

// curX curY가 같은 값이 되면 우리가 찾는 수일 것.
while (curX != curY)
{
// 단순하게 더 작은 쪽을 더해주는 방식으로 진행.
    // 달력을 1씩 더해주는 대신 뭉탱이로 더했다고 생각하였다.
    if(curX < curY)
    	curX += M;
    else
    	curY += N;
}

// curX를 출력해도 동일
Console.WriteLine(curY);

k = x + a x 10

k = y + b x 12

 

앞에서 살펴봤던 식이다.

더해나가며 a, b에 도달하는 것이다.

 

 

전체 코드

internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int T = int.Parse(reader.ReadLine());

            for (int i = 0; i < T; i++)
            {
                string[] inputs = reader.ReadLine().Split();
                int M = int.Parse(inputs[0]);
                int N = int.Parse(inputs[1]);
                int x = int.Parse(inputs[2]);
                int y = int.Parse(inputs[3]);

                int abs = Math.Abs(x - y);
                int gcd = GCD(M, N);
                int lcm = LCM(M, N);

                if (abs % gcd != 0)
                    print.WriteLine("-1");
                else
                {
                    int curX = x;
                    int curY = y;
                    while (curX != curY)
                    {
                        if(curX < curY)
                            curX += M;
                        else
                            curY += N;
                    }

                    print.WriteLine(curY);
                }
            }
        }

        private static int GCD(int value1, int value2)
        {
            int smallValue = value1 < value2 ? value1 : value2;
            int maxMeasure = 1;

            for (int i = 2; i <= smallValue; i++)
            {
                if (value1 % i == 0)
                {
                    if (value2 % i == 0)
                    {
                        maxMeasure = i;
                    }
                }
            }

            return maxMeasure;
        }

        private static int LCM(int value1, int value2)
        {
            return (value1 * value2 / GCD(value1, value2));
        }
    }