[백준 / BOJ / SILVER 1] 6064 번 : 카잉 달력

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

6064번: 카잉 달력

문제 접근 방식

• x나 y를 1씩 증가시키는 방식으로 진행 시 시간초과를 초래할 수 있다.
• x를 고정 시키고 출력 해를 M만큼 증가시키는 방식으로 해를 구한다.
• 증가하는 해에 대해서 %N을 이용하여 일치하는 y를 찾는다.

예를 들어 M과 N이 10, 12 이고 x와 y가 3,1일 때

<10, 12>

1번째 해 -> <1,1>

2번째 해 -> <2,2>

3번째 해 -> <3,3>

.........

10번째 해 -> <10,10>

11번째 해 -> <1,11>

12번째 해 -> <2,12>

13번째 해 -> <3,1>

 

13이 출력해야 할 해임을 알 수 있다.

이때 x를 고정했다고 가정하면 1번째 x==3이 일치하는 것은 3번째 해이고 그 다음은 13번재 해이다.

이는 x + M * i로 볼 수 있다. 이 때 (x + M * i )%N이 해당 년의 y값이 되므로, 구한 y값과 입력 받은 y값이 일치한다면 그 때를 답이라고 볼 수 있다.

 

여기서 주의해야할 점은 %를 이용하기 때문에 0부터 시작이 되므로 (M,N) 과 (x,y)가 일치할 때 문제가 생길 수 있다.

그렇기 때문에 최초 x와 y를 -1을 해준뒤 구해진 해에 1을 더하는 식으로 문제를 해결해야 한다.

 

아래는 코드입니다.

#include <iostream>
 
using namespace std;
 
void solve(int M, int N, int x, int y)
{
    x--;
    y--;
 
    for (int i = 0; i < N; i++)
    {
        int ans = M * i + x;
 
        if (ans % N == y)
        {
            cout << ans + 1 << "\n";
            return;
        }
    }
    cout << "-1\n";
 
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T, M, N, x, y;
 
    cin >> T;
 
    for (int i = 0; i < T; i++)
    {
        cin >> M >> N >> x >> y;
        solve(M, N, x, y);
    }
 
    return 0;
}

문제 출력이 다양하지 않으므로 반례를 준비했습니다.

15
40000 39999 39999 39998
40000 39999 40000 39999
40000 40000 40000 39999
40000 39998 40000 39997
39999 2 39998 2
3 40000 3 39999
40000 3 40000 3
8 2 4 2
10 12 2 12
12 10 12 10
12 10 1 1
12 6 12 6
10 1 5 1
1 10 1 5
1 1 1 1
 
답:
1599959999
1599960000
-1
-1
39998
39999
120000
4
12
60
1
12
5
5
1