[백준] 6064번 카잉 달력 C++ 풀이

---

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 정수론
• 중국인의 나머지 정리

---

문제 설명

최근에 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을 출력한다.

---

예제 입력

3
10 12 3 9
10 12 7 2
13 11 5 6

---

예제 출력

33
-1
83

---

아이디어

주어진 m과 n으로 만들 수 있는 마지막 해는 두 수의 최소 공배수이다.

주어진 x와 y에 도달하기까지 걸리는 해가 몇 번째 해인지 구하기 위해서

우선 x를 i에 고정하고 1회 반복마다 m을 더해주고 임시 변수 ty에 i % n을 저장하면서 최소 공배수에 도달할 때까지 y와 일치하는지 비교한다.

만약 ty가 0이라면 이는 i % n의 값이 0이라는 의미이므로 최대값을 넣어줘야 한다.

ty와 y가 일치할 때의 i 값이 정답이다.

---

알고리즘

a와 b의 최소 공배수를 구하기 위해서는 최대 공약수를 먼저 구하고

(a * b / a, b의 최대 공약수)를 통해서 최소 공배수 max를 구한다.

 

이후는 위의 아이디어와 동일한 과정으로 진행된다.

---

코드

#include <iostream>
using namespace std;
int gcd(int a,int b)
{
    int r;
    while(b != 0)
        {
            r = a % b;
            a = b;
            b = r;
        }
    return a;
}

int lcm(int a, int b)
{
    return (a * b) / gcd(a,b);
}

int main() {
    int T;
    cin>>T;
    while(T--)
        {
            int m,n,x,y,result=-1;
            cin>>m>>n>>x>>y;
            int max = lcm(m,n);
            for(int i = x ; i <= max ; i+=m)
                {
                    int ty = i % n;
                    if (ty == 0) ty = n;
                    if(ty == y) 
                    {
                        result = i;
                        break;
                    }
                }
            cout << result <<"\n";
        }
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/6064

처음에는 최대 공약수 최소 공배수 관계를 생각하지 못하고 x나 y를 고정하는 것에 꽂혀서 x, y를 열심히 고정해 보려고

시도했으나 답은 나왔지만, 너무 느려서 시간을 초과했다.

이후 최대 공약수까지 반복하는 것과 x를 고정하고 y를 비교하는 것 그리고 ty == 0일 때 ty = n을 해줘야 한다는 것을 알게 되었고 문제를 풀 수 있었다.

풀고 나면 그리 어려운 문제는 아니지만 이런 아이디어가 없다면 시간 초과가 되는 경우가 빈번한 것 같다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!