[BOJ] 6064 카잉 달력

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

6064번: 카잉 달력

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

mathematics

 

---------------------------------------------------풀이----------------------------------------------------

 

<x:y>는 임의의 수 a, b에 대해, M*a+x = N*b+y를 만족하는 최솟값이 정답이다.

예를 들어, M=10, N=12이면,

<3:1> = 10*1+3 = 12*1+1 = 13이고,

<1:11> = 10*1+1 = 12*0+11 = 11이다.

이 값을 찾을때까지 a와 b를 증가시켜가며 찾는다.

calc_gcd()를 통해 N과 M의 최소공배수가 최대 해의 수이므로 그 값을 넘어가면 종료조건으로 두도록 했는데,

gcd를 찾는 과정 대신 N*M을 리턴하도록 간단하게 구현했음에도 큰 문제 없이 통과되었다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <deque>

using namespace std;

int calc_gcd(int n, int m){
    return n*m;
}

// 첫 번째 해 : <1:1> 두 번째 해 : <2:2>
// <x:y>의 다음 해 = <x':y'>
// x < M이면 x' = x+1 아니면 x' = 1
// y < N이면 y' = y+1 아니면 y' = 1
// <M:N>은 마지막해를 나타냄.
// <x:y> = M*k+x = N*l+y
// M = 10, N = 12일 때,
// <1:11> = 10*k+1 = 12*l+11 = 11 => k는 1, l은 0.
// <3:1> = 10*k+3 = 12*l+1 = 13 => k는 1, l은 1.
// <10:12> = 10*k+10 = 12*l+12 = 60 => k는 5, l은 4.
int main(void){
    FASTIO;
    int T;
    cin >> T;
    while(T--){
        int M, N, x, y;
        cin >> M >> N >> x >> y;
        // k는 <x:y>가 k번째 해를 나타내는 것을 의미.
        // <x:y>에 의해 표현되는 해가 없으면(유효하지 않은 표현이면) -1 출력
        int k = 1;
        int curx = x, cury = y;
        int gcd = calc_gcd(N, M);
        while(curx != cury){
            // 유효하지 않은 값이면 종료
            if(curx > gcd || cury > gcd){
                curx = -1;
                break;
            }

            // 유효한 값을 찾아 계속하기
            if(curx < cury){
                curx += M;
            }
            else{
                cury += N;
            }
        }
        cout << curx << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

<1:1>부터 끝까지 탐색하는 방식은 매우 초반에 시간초과였다.

따라서 방법을 바꿔 규칙을 찾아보았다.

 

gcd를 찾는 방법을 구현은 안 했는데, 알아두긴 하자~!!