백준 6064번 : 카잉 달력

백준 6064번 : 카잉 달력

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

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int count = Integer.parseInt(br.readLine());

        for(int i = 0; i<count; i++){
            boolean check = false;
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken()) -1;
            int y = Integer.parseInt(st.nextToken()) -1;
            for(int j = x; j<lcm(m, n); j+=m){
                if(j%n ==y){
                    sb.append(j+1).append("\n");
                    check = true;
                    break;
                }
            }
            if(!check){
                sb.append("-1").append("\n");
            }
        }
        System.out.println(sb);
    }

    public int gcd(int a, int b){
        return b==0?a:gcd(b, a%b);
    }
    public int lcm(int a, int b){
        return (a*b)/gcd(a,b);
    }
    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

날짜 계산(https://mokggang.tistory.com/13) 으로 풀었더니 시간 초과가 나왔다. 그래서 어떻게 풀지 하면서 규칙을 열심히 찾다가 어느 순간 구글을 열심히 찾는 나를 발견한다. 참고한 사이트(https://1-7171771.tistory.com/38) 계산에는 규칙이 존재 했고, 그 규칙에 맞게 계산식을 넣으면 된다.

 

풀이 결론

x는 m만큼 증가할때마다 값이 똑같고 y만 다르다. 이건 반대로도 마찬가지다.

y는 n만큼 증가할때마다 값이 똑같고 x의 값만 다르다. 

예시) m = 10, n = 12 , x = 3 , y = 9

 

x+m = 13 = 3       

x+m*2 = 23 = 3   

y+0 = 9 = 9

y+n =  21 = 9

 

1 : (1, 1)     6 : (6, 6)      11 : (1, 11)       16 : (6, 4)        21 : (1, 9)

2 : (2, 2)     7 : (7, 7)      12 : (2, 12)       17 : (7, 5)        22 : (2, 10)

3 : (3, 3)     8 : (8, 8)      13 : (3, 1)         18 : (8, 6)        23 : (3, 11)

4 : (4, 4)     9 : (9, 9)      14 : (4, 2)         19 : (9, 7)        24 : (4, 12)

5 : (5, 5)    10 : (10, 10)  15 : (5, 3)        20 : (10, 8)        25 : (5, 1)

 

결국 마지막 해(최소공배수)까지 루프를 돌려서 x의 값을 고정해놓고, y의 값을 찾아서 입력과 동일할 경우

출력해준다. 단, 여기서 구하고자 하는 해의 %n==y 가 0일 경우가 존재하기 때문에 x와 y의 값에 -1 해주고, 출력 결과에 +1 해준다. 그리고 마지막 해까지 조건을 통과하지 못하면 -1 를 출력해주면 된다.