[백준, 자바, 6064번] 카잉 달력

풀이

• 해당 문제는 처음에 무슨 말인가 하고 
• 쭉 보다보니 x,y가 서로 독립적으로 변하는 문제인 것을 확인
• 이후 우선 단순히 1씩 증가하고 M과N위를 벗어날 경우
• 나머지를 활용하여 해결하고자 함.
• 다만 이렇게 하니 시간 초과가 발생...
• 역시나 정답 비율이 낮은 이유는 있다는 것을 느낌
• 그래서 어떻게 해결할 수 있을지 고민하다가
• 뭔가 규칙을 발견하게 됨.
• 우선 아래 코드를 보면
  • 입력 값이 10 12 3 9의 경우엔
    
    • x를 기준으로 y를 변경 후
    • M만큼 계속 y에 더하고 초과 시 나머지로 변경한다면
    • 간단히 해결이 됨
  • 입력 값이 10 12 7 2의 경우엔
  • 출력이 -1로 나오는 것으로 해결 방법에 대해 고민해 본 결과
  • 우선 공통적으로 x가 y보다 작은 값이 들어가도록 조건 처리하기
  • 이후 마찬가지로 10 12 3 9 입력 값처럼 연산을 하지만
  • 가장 마지막 줄에 14 20 (2 10) 이후 다시 (2 2) 가 나오는 것을 확인 후
  • y의 값이 계속 반복되는 것을 확인
  • 그래서 Set을 통해서 y의 값을 추가하며
  • 변경된 y의 값이 Set에 존재할 경우 탈출하도록 하여 해결.
• 이렇게만 하니 또 틀렸다고 나와서
• 입력 값을 아래와 같이 넣어보니 
  • 1
  • 1 1 1 1
• 원하는 1의 값이 출력이 안되어 조건 처리한 결과
• 아주 힘겹게 퍼센트가 올라가며 해결 완료

// 10 12 3 9
// 1 1 -> 3 3 -> 13 13 (3 1) -> 13 11 -> (3 11) -> 13 21 (3 9)

// 10 12 7 2
// 12 10 2 7
// 1 1 -> 2 2 [2]-> 14 14 (2 4) [14]-> 14 16 (2 6) [26]-> 14 18 (2 8) 
//	-> 14 20 (2 10) -> 14 22(2 2) -> 14 14 (2 2)

 

// 성공 코드

import java.io.*;
import java.util.*;

public class _6064 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        while (T>0) {
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            if (x>y) {
                int tmp1 = M;
                int tmp2 = x;
                M = N;
                x = y;
                N = tmp1;
                y = tmp2;
            }

            int result = findKaing(M,N,x,y);
            bw.write(result+"\n");
            T--;
        }
        bw.flush();
    }

    private static int findKaing(int M, int N, int x, int y) {
        Set<Integer> s_li = new HashSet<>(Arrays.asList(x));
        int cnt = x;
        int now = x;
        boolean state = false;
        if (x!=y) {
            while (true) {
                now=(now+M)%N==0?N:(now+M)%N;
                cnt+=M;
                if (now==y) {
                    state = true;
                    break;
                } else if (s_li.contains(now)) break;
                s_li.add(now);
            }
        } else state = true;
        return state?cnt:-1;
    }
}

 

// 시간초과 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        while (T>0) {
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int result = findKaing(M,N,x,y);
            bw.write(result+"\n");
            T--;
        }
        bw.flush();
    }

    private static int findKaing(int M, int N, int x, int y) {
        int cnt = 1;
        int[] now = {1,1};
        boolean state = x==M&&y==N;
        while (now[0]!=M || now[1]!=N) {
            if (now[0]==x && now[1]==y) {
                state = true;
                break;
            }
            now[0]=now[0]+1>M?1:now[0]+1;
            now[1]=now[1]+1>N?1:now[1]+1;
            cnt++;
        }
        return state?cnt:-1;
    }
}