[BOJ] 백준 6064 카잉달력 c++ 코드/풀이

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

6064번: 카잉 달력

 

 

문제해설

 

연도 표시를 x:y 의 형식으로 표현함(x <= M, y <= N)

x:y가 올해, x':y'가 다음 해인 경우, x < M이면 x' = x+1, 그렇지 않으면 x'=1

-> 이 부분이 바로 이해가 되지 않을 수 있으나 간단함

현재 x와 y가 각각 M과 N보다 작으면 다음 해를 표기할 때 1을 증가시키면 되고, x=M, y=N이면 x'=1, y'=1이 다음 해가 됨

 

ex) M=10, N=12 일 때,

1:1(1년) -> 2:2(2년) -> 3:3(3년) ..... 10:10(10년) -> 1:11(11년) 이런식으로 증가함

 

문제풀이

 

최초 풀이에는 아무 생각없이 브루트 포스로 x,y에 도달 할 때까지 반복문을 돌리고 도달할 때 출력하도록 구현 했었지만 바로 시간초과!

계산해보니 M과 N이 최대 40,000까지 입력된다고 했을 때, 최악의 경우 16억번 연산하므로 절대 불가능

 

이후에 태그의 "중국인의 나머지 정리"를 참고하여 풀었음(참고로 개념자체는 이해못했음 ㅋㅋ)

결국 우리가 찾고자 하는 것은 <x:y>의 형태로 나타낼 수 있는 연도가 몇번째 해인지

여기서 x는 M까지 증가하고, y는 N까지 증가함.

 

따라서 x와 y의 증가 패턴은
x: 1, 2, 3, ..., M, 1, 2, 3, ...
y: 1, 2, 3, ..., N, 1, 2, 3, ...
이렇게 두 수가 증가하면서 우리가 원하는 <x:y>의 형태를 찾아야 하지만 저런식의 순차탐색은 시간초과가 발생

따라서, x값을 고정시키고 M만큼 증가시키면서 y값이 우리가 원하는 값과 일치하는지 확인하면 됨

방법 설명

x부터 시작 (x는 주어진 값)
x를 N으로 나눈 나머지가 y와 일치하는지 확인
일치한다면, 그 시점의 x가 우리가 찾는 연도
일치하지 않는다면, x에 M을 더해줌
이 과정을 x가 M * N을 초과할 때까지 반복

 

x를 M씩 증가시키면서 y값을 확인하는 것은, 사실상 y의 값만을 바꿔가며 확인하는 것과 동일함

따라서, 이렇게 확인하면 최대 N번 안에 정답을 찾을 수 있음

예시
M = 10, N = 12, x = 3, y = 9 일 때

x = 3  -> 3을 12로 나눈 나머지는 3이므로 y와 일치하지 않음
x에 10을 더하면 x = 13, 13을 12로 나눈 나머지는 1
다시 x에 10을 더하면 x = 23, 23을 12로 나눈 나머지는 11
다시 x에 10을 더하면 x = 33, 33을 12로 나눈 나머지는 9이므로, y와 일치함

따라서 33이 우리가 원하는 정답이 됨

 

 

코드

#include <bits/stdc++.h>
#define PRESET ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

/*
    그냥 브루트 포스로 구현 -> 시간초과 대충 16억 넘음
    중국인의 나머지 정리 적용-> 최대 N의 시간 안에 연산 완료 가능
    1. x부터 시작, x를 N으로 나눈 나머지가 y와 일치하는지 확인 -> 일치하면 지금의 x가 정답
    2. 일치하지않는 다면 x에 M을 더해줌
    3. 위 과정을 x가 M*N을 초과할 떄 까지 반복
    4. y가 n과 같을 경우 x%n은 0이 되는것을 방지
*/

int main(){
    PRESET;
    
    int t;

    cin >> t;

    while(t--){
        int m, n, x, y, ans = -1;

        cin >> m >> n >> x >> y;

        while(x <= m * n){
            if(x % n == y % n){
                ans = x;
                break;
            }
            else x += m;
        }

        cout << ans << "\n";
    }
}