백준 6064 카잉 달력 c++ [컴공과고씨]

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

6064번: 카잉 달력

 

문제 정리

몇번 째 해인지 나타내는 방법을 <x,y>라고 정의

여기서 x와 y의 최대값이 문제에서 주어짐.

예를 들어 m = 10, n = 12 라는 것은 x의 최대값은 10 y의 최대값은 12

1번째 해 = 1,1

2번째 해 = 2,2 

이런식으로 해가 최대값을 넘지 않으면 +1 씩 증가

그러다가 최대값을 넘어가면 1로 다시 시작 

10번째 해 = 10, 10

11번째 해 =   1, 10 

이렇게 넘어감. 이 때 만약 둘다 동시에 최대값이 되면 최대 해가 되어서 더 이상의 해는 없음.

이때 x, y가 주어질 때 그때가 몇 번째 해인지 구하라.

 

문제 해결 방법

문제를 보시면 알겠지만 1씩 증가시키면서 일일이 하면 시간초과가 날것입니다.

이 문제는 2가지 방법으로 풀 수 있습니다.

 

1. 덧셈과 뺄셈을 이용해서 푸는 법.

2. 최대공약수와 최소공배수를 이용하여 나눗셈을 이용한 방법.

 

저는 처음 문제를 풀 때 1번 방법을 이용해서 풀어주었습니다.

물론 2번 방법도 설명해드리고 코드도 올려드렸습니다.

 

1번 방법

먼저 1번 방법 같은 경우 간단하게 1씩 증가시키는 방법에서 시간을 줄이기 위해서 1씩 증가시키는 것이 아니라

x,y 둘 중에 최대값이 빠르게 되는 것을 뺄셈을 통해 최대값으로 만들어주고 1로 초기화하여서 정답을 비교해주는 방법입니다.

예를 들어서 m =10, n=12일 때 x와 y는 1부터 시작함으로 

최대값이 되기 위한 값은 x는 10-1 = 9, y는 12-1=11 이기때문에 9번째 해에 x는 최대값을 도달하게 되고 10해에 x=1로 초기화가 됩니다. 그렇기 때문에 1씩 증가시키는 것이 아니라 10을 더해서 <1,11>을 만들어주는 것입니다.

그다음은 반복입니다. x는 10 - 1 = 9, y는 12-11 = 1 이기 때문에 y가 더 작습니다. 그래서 y가 1로 초기화가 될 수 있도록

2를 증가시켜 <3,1>로 만들어 줍니다.

여기서 우리는 항상 어떠한 값을 1로 맞추어 주기 때문에 정답이 <3,9>라면 <1,7> 즉, 하나가 1이 되는 순간을 타겟으로 삼아 주고 <1,7>가 되는 해를 구한 후 정답인 <3,9>가 되도록 해를 뺄셈을 통해 구해줍니다.

여기서도 1씩 증가시키는 것은 최대값이 크면 반복횟수가 많아짐으로 뺄셈을 통해 구해주는 것입니다. 

말로 하면 복잡하지만 코드로 보면 굉장히 쉽습니다. 

 

2번 방법

이 방법도 간단하게 구현할 수 있습니다.

일단 보시면 알겠지만 m=10, n=12라고 하면 만약 51번째 해를 <x,y>로 표현하려면 어떻게 해야할까요?

최대값으로 나눈 나머지가 되겠죠?

51은 10이 몇번? 5번 들어가고 그 후 1해가 지난가면 51번째입니다. x=1

51은 12가 몇번? 4번 들어가고 그 후 3해가 지나가면 51번째이기 때문에. y= 3 이겠죠.

주의해야 할 것은 나머지가 0이면 최대값으로 바꾸어주어야합니다.

예를 들어 50번째 해는 x로 표현하면 10이겠죠? 

멸망해는 어떻게 되냐면 m과n의 값이 동시에 나누어지는 최소값이 멸망해가 되겠죠?

즉, 멸망해는 m과 n의 최소공배수가 됩니다.

 

그러면 우리는 구하려는 x가 3이라고 하면 x가 3이 되는 해에서 y 값을 구해서 구하려는 y와 맞는지 비교만 하면 됩니다.

m=10일때 x가 3이 되는 해는? 10을 계속 더해주면 됩니다. 3 13 23 이렇게 가면 x값이 3인 해가 되겠죠?

그럼 3번째 해 일때 n=12라고 하면 y는 3을 12로 나눈 나머지 3 이겠고 13번째 해는 12로 나누어주면 1이겠고

이렇게 되겠죠 그래서 정답인 y와 같아지면 해를 찾을 수 있고 없으면 -1를 출력해주면 됩니다.

 

 

전체 코드(1번 방법)

#include <iostream>
using namespace std;
int main(){
    int T;
    cin >> T;
    for (int t = 0; t < T;t++){
        int m, n, x, y;
        cin >> m >> n >> x >> y;
        int rx, ry; // 타겟 x,y를 구해줌 어느 한 쪽이 1이 되도록
        if(x > y){ // y가 1인 경우
            rx = x - y + 1;
            ry = 1;
        }
        else{ // x가 1인 경우
            ry = y - x + 1;
            rx = 1;
        }
 
        int cnt = 1; // 몇 번째 해
        int nx = 1; // 다음 번째 x
        int ny = 1; // 다음 번째 y
        bool stop = false; // 멸망해 이거나 정답을 찾았거나
        while(!stop){
            //다음해가 타겟 x와 같은 경우 -> 정답
            if(nx == rx && ny == ry){ 
                cnt = cnt + x - rx; // 정답해로 갈 수 있도록 더해줌
                nx = x;
                ny = y;
                stop = true;
            }        
            else if(m - nx < n - ny){// x가 먼저 1이되는 경우
                ny = ny + m - nx + 1;
                cnt = cnt + m - nx + 1;
                nx = 1;  
            }else if(m - nx > n- ny){ // y가 먼저 1이 되는 경우
                nx = nx + n - ny + 1;
                cnt = cnt + n - ny + 1;
                ny = 1;
            }else{ // 멸망해인 경우
                cnt = cnt + n - ny;
                nx = m;
                ny = n;
                stop = true;
            }
        }
        if(nx == x && ny == y){ // 정답 해
            cout << cnt << endl;
        }else{ // 멸망해까지 없는 경우
            cout << -1 << endl;
        }
    }
    return 0;
}

 

2번째 방법

#include <iostream>
using namespace std;
 
int gcd(int a, int b){ // 최대 공약수
    if(b==0)
        return a;
    return gcd(b, a % b);
}
int lcm(int a, int b){ // 최소 공배수
    return (a * b) / gcd(a, b);
}
int main(){
    int T;
    cin >> T;
    for (int t = 0; t < T; t++){
        int m, n, x, y;
        int result = -1;
        cin >> m >> n >> x >> y;
        int maxi = lcm(m, n); // 멸망해
        for (int i = x; i <= maxi; i+=m){
            int ny = i % n; // y값
            if(ny == 0) // 이때는 y가 최대값이 됨
                ny = n;
            
            if(ny == y){ // 정답
                result = i;
                break;
            }
        }
        cout << result << '\n';
    }
    return 0;
}