실1 6064 카잉달력 - 브루트포스 건너뛰며해보기

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

6064번: 카잉 달력

 

 

//카잉달력
public static void bf_6064(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    int t = Integer.valueOf(bf.readLine());
    while (t-- > 0) {
        String[] line = bf.readLine().split(" ");
        int m = Integer.valueOf(line[0]);
        int n = Integer.valueOf(line[1]);
        int x = Integer.valueOf(line[2]) -1;
        int y = Integer.valueOf(line[3]) -1;
        boolean ok = false;

        // 1. n*m => 전체 시행횟수
        // 그런데 값이 +1 되는게 아니라 m만큼 "건너 뛰며 해보기" 방식이므로 시간복잡도는 O(mn) 이 아니라 O(n)이 된다.
        // O(mn)의 경우 4만*4만=16억=1.6초 이므로 시간제한에 걸린다.

        // 2. int k = x => k의 초기값은 x
        // 계산의 편의를 위해 x와 y는 -1씩 해주었으며, 마지막에 결과값에서 +1 해준다.

        // 3. k+=m => m의 배수
        for (int k = x; k < n*m; k+=m) {
            if (k%n == y) {
                System.out.println(k+1);
                ok = true;
                break;
            }
        }
        if (!ok) {
            System.out.println(-1);
        }
    }
}