[수학] 카잉 달력(6064) (C++)

 

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

6064번: 카잉 달력

 

1. 문제 개요

 

카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

 

 

2. 입출력

 

 

3. 문제 풀이

 

M=12, N=10 일 때 카잉 달력의 표기는 다음과 같다.

 

이때 x가 3일 때 y의 값은 3, 1, 11, 9 ... 등등이다.

따라서 우리가 x=3이고 y=9일 때 해를 찾고싶다면 x가 첫번째로 3이 될 때부터 년도값을 차례로 증가해가며 y값을 확인해보면 된다.

3, 13, 23, 33, 43 ... 과 같은 순서로 년도를 증가해가며 이를 N으로 나눈 값이 y 값과 일치하게 되면 출력해준다.

 

for(j=x;j<=max;j+=M){
      int temp = j%N;
      if(temp==0) temp = N;
      if(temp == y) {
          cout << j << "\n";
          break;
      }
}

 

이때 루프가 무한히 돌아가는 것을 방지하기 위해 종말의 해를 찾아주어 루프가 종말의 해 전까지만 돌아가도록 해주면 된다.

종말의 해는 M과 N의 최소공배수이므로 다음과 같이 구해주면 된다.

 

int gcd(int a, int b){
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
} // 최대공약수

int lcm(int a, int b) {
    return a * b / gcd(a, b);
} // 최소공배수

 

루프가 다 돌아가고 난 뒤에도 년도 값을 찾지 못했다면 -1을 출력해준다.

 

 

4. 전체 코드

 

#include<iostream>

using namespace std;

int gcd(int a, int b){
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
} // 최대공약수

int lcm(int a, int b) {
    return a * b / gcd(a, b);
} // 최소공배수

int main(void)
{
    int num;
    int M, N, x, y;
    cin >> num;
    
    for(int i=0;i<num;i++){ // 테스트케이스 수
        cin >> M >> N >> x >> y;
        int max = lcm(M,N); // 종말의 해
        int j;
        for(j=x;j<=max;j+=M){
            int temp = j%N;
            if(temp==0) temp = N;
            if(temp == y) {
                cout << j << "\n";
                break;
            }
        }
        if (j > max) // <x:y>에 의해 표현되는 해가 없는 경우
            cout << -1 << "\n";
    }
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!