Baekjoon 6064번 카잉 달력

문제

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

걸린 시간

02 : 08 : 48 실패

풀이

Python3

def GCD(M, N):
    while N != 0:
        r = M % N
        M = N
        N = r
    return M

def LCM(M, N):
    return M*N/GCD(M, N)

if __name__ == "__main__":
    T = int(input())

    for _ in range(0, T):
        M, N, x, y = map(int, input().split())

        ans = x
        y %= N
        lcm = LCM(M, N)
        while ans <= lcm and ans%N != y:
            ans += M

        if ans > lcm:
            print(-1)
        else:
            print(ans)

2시간 넘게 고민했지만 방향을 잘못 잡아서 엉뚱한 규칙을 찾고 있었다.

정답을 보니 달력의 해를 M과 N으로 각각 나눈 나머지가 x와 y임을 이용해 풀 수 있다고 한다.

처음의 해를 x값으로 설정해두고 한번 반복할 때마다 해를 M만큼 증가시켜가며 N으로 나눈 값이 y와 동일한지를 검사하면 정답을 찾을 수 있다.

1씩 값을 증가시켜가며 해를 찾는 고지식한 방법을 처음 시도해보고 시간을 줄이기 위해 M 혹은 N 씩 건너뛰는 방법까진 생각했는데 위의 규칙을 찾아내지 못해 문제를 풀지 못했다. 만약 찾았더라도 x와 y가 각각 M, N일때의 경우를 생각하지 못해 결국 포기했을 것 같다.

만약 기준이 되는 수가 최대값과 동일하게 주어졌을 경우가 반례이다. x, y 값은 1부터 시작하므로 나눈 나머지가 0이 되었을 때 틀린 값이 출력되는 것이다.

y %= N
x %= M

위와 같은 조건을 추가해 범위를 0 <= x < M or 0 <= y < N 으로 바꾸어주어야 한다.

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int m, n, x, y;
        cin >> m >> n >> x >> y;
        int rx = x, ry = 0;
        int end = lcm(m, n);
        int day = rx+ry*m;
        while(true){
            if(day%n == y%n || day > end) break;
            ry++;
            day = rx+ry*m;
        }
        if(day > end) cout << -1 << "\n";
        else cout << day << "\n";
    }
    return 0;
}

반년이 지난 지금은 혼자 힘으로 풀어내긴 했지만 아직도 인덱싱 넘버링은 어렵다.

참고

• Baekjoon(백준) : 6064번(카잉 달력) - 맨땅에 코딩