[BF] 6064번 카잉 달력

6064번 카잉 달력

 

https://www.acmicpc.net/problem/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을 출력한다.

 

예제 입력

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

 

예제 출력

33
-1
83

 

해결방법

🔥컴파일 에러🔥

2차원 배열을 만든 뒤, 거기에 모든 날짜의 경우를 저장하였다

만약 x = 7, y = 8 이면 실제 년도는 d[7][8] 에 저장되는 것이다

하지만 컴파일 에러가 발생했다

아마 2차원 배열의 크기가 너무 크기때문일까....??

cin >> testcase;
for(int t=0; t<testcase; t++){
    cin >> m >> n >> x >> y;
    for(int k=0; k<MAX; k++)
        memset(d[k], -1, sizeof(d[k]));
        
        i = 1;
        j = 1;
        year = 1;
        while(true){
            d[i][j] = year;
            
            if(i==m && j==n) break;
            
            i++; j++; year++;
            
            if(i>m) i = 1;
                if(j>n) j = 1;
                    }
    
    cout << d[x][y] << endl;
}

 

⏱시간 초과⏱

굳이 2차원 배열을 사용할 필요가 없었다.

그래서 이번에는 i==x && j==y 의 경우 바로 출력을 하도록 하였다.

하지만 이번에는 시간초과가 발생했다.

이러한 시뮬레이션은 x와 y를 각각 ++ 시키면서 증가한다.

이 경우에는 O(M*N)의 시간복잡도가 나오게 되어 시간초과가 발생한다.

 

cin >> testcase;
for(int t=0; t<testcase; t++){
    cin >> m >> n >> x >> y;
    
    i = 1;
    j = 1;
    year = 1;
    while(true){
        if(i==x && j==y){
            cout << year << endl;
            break;
        }
        if(i==m && j==n){
            cout << -1 << endl;
            break;
        }
        
        i++; j++; year++;
        
        if(i>m) i = 1;
        if(j>n) j = 1;
    }
}

 

⭐️맞았습니다!!⭐️

시간초과를 해결하기 위해서 폭풍검색을 했다 (참고 블로그)

내가 한 경우는, x의 경우와 y의 경우를 모두 처리했기 때문에 시간복잡도가 O(M*N) 이었지만 다른 방법이 존재했다

 

핵심 아이디어는 x를 먼저 고정시키고 y를 맞춰보는 것이다!

ex) M:N <13:11> , X:Y <5:6>

i	y 식	j
5	5 % 11	5
18	18 % 11	7
31	31 % 11	9
44	44 % 11	0 ➝ 11
57	57 % 11	2
70	70 % 11	4
83	83 % 11	6
96	96 % 11	8

위 처럼 i 는 초기값을 x 값으로 설정한 뒤, m만큼 증가시킨다

i값을 n으로 나눈 값을 j로 할당을 하는데, 만약 j값이 y와 같다면 i가 해당년도가 된다 (만약 i%n==0 이라면 j=n)

 

또한, M과 N의 마지막년도는 M과 N의 최소공배수인데 이는 유클리드 호제법을 사용했다

// gcd : 최대 공약수
int gcd(int a,int b){
    // a에 항상 큰 값을 위치시키기 위함
    int tmp;
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    // 유클리드 호제법
    while(b!=0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

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

 

만약 i가 마지막년도보다 크다면 -1을 출력하도록 하였다

cin >> testcase;
for(int t=0; t<testcase; t++){
    cin >> m >> n >> x >> y;
    
    int last = lcm(m,n);
    i = x;
    while(i<=last){
        j = i % n;
        if(j == 0) j = n;
            if(j == y) break;
        i += m;
    }
    if(i > last) cout << -1 << endl;
    else cout << i << endl;
}

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 0
#define INF 987654321
using namespace std;

int testcase;
int m,n;
int x,y;
int i,j;

// gcd : 최대 공약수
int gcd(int a,int b){
    // a에 항상 큰 값을 위치시키기 위함
    int tmp;
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    // 유클리드 호제법
    while(b!=0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

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

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=0; t<testcase; t++){
        cin >> m >> n >> x >> y;
        
        int last = lcm(m,n);
        i = x;
        while(i<=last){
            j = i % n;
            if(j == 0) j = n;
            if(j == y) break;
            i += m;
        }
        if(i > last) cout << -1 << endl;
        else cout << i << endl;
    }
    
    return 0;
}