[Baekjoon] 6064: 카잉 달력

문제

1 1 부터 시작하여 각각 m과 n에 대한 모듈로 연산을 진행하여 x y가 될 때 까지 몇번이 걸리는지 구하는 문제이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q6064 {

    private static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            String[] nmxy = br.readLine().split(" ");
            int m = Integer.parseInt(nmxy[0]);
            int n = Integer.parseInt(nmxy[1]);
            int x = Integer.parseInt(nmxy[2]);
            int y = Integer.parseInt(nmxy[3]);
            int gcd;
            if (m > n) {
                gcd = gcd(m, n);
            } else {
                gcd = gcd(n, m);
            }
            int lcm = m * n / gcd;

            int tempx = x;
            int tempy = x;
            boolean seek = false;
            while (tempx <= lcm) {
                tempy = tempx % n == 0 ? n : tempx % n;
                if (tempy == y) {
                    seek = true;
                    break;
                }
                tempx += m;
                tempy %= n;
            }

            sb.append(seek ? tempx : -1).append("\n");
        }

        System.out.print(sb);
    }

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

시간을 줄일 방법이 생각나지 않아 결국 검색을 통해 해결했다.

아이디어는 초기 값이 x인 두 수 a, b를 놓고 a와 b를 m만큼 계속 증가시켜주며 b를 n에 대한 모듈로 연산을 통해 y와 같을 때까지 찾아 나가는 것이다.

 

예를 들어 m, n, x, y가 각각 10 12 3 9 라고 하면

a = 3, b = 3부터 시작하여

a = 13, b = 13 % 12 = 1

a = 23, b = 11 % 12 = 11

a = 33, b = 21 % 12 = 9

로 a가 33일때 b의 값이 y와 같아진 것을 확인할 수 있다.

 

단, a의 수가 두 수의 최소공배수를 넘어가면 없는 것으로 체크하고 -1을 출력한다.

 

회고

시간을 줄일 아이디어를 떠올리는 것이 아직 너무 어려운 것 같다.

많은 문제를 풀어보며 효율적인 알고리즘에 대해 좀 더 신경 써야될 것 같다.