[JAVA] 백준 6064 - 카잉 달력

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

6064번: 카잉 달력

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while(T-->0){
            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;

            int year = x;
            int answer= -1;

            while(year < N * M){
                if(year % N == y){
                    answer = year + 1;
                    break;
                }
                year += M;
            }
            System.out.println(answer);
        }

    }
}

 

 

year를 1씩 증가시키며 와일문으로 돌리니, 역시나 시간초과가 나버렸다.

최악의 경우 시간복잡도가 O(N*M) 즉 16억이나 된다. 

정답률이 왜 20퍼인지 알 수 있는 문제였다 어려웠다... 

 

M=10, N=12, x=3, y=3 이라고 하자

 

3년: <3:3>

13년: <3:1> 

23년: <3:11>

.

.

시간 복잡도를 줄여보자.

 

x가 M씩 증가할때마다 x값은 동일하고 y값이 변하는 것을 볼 수 있다.

(반대로 y가N씩 증가할때마다 y값은 동일하고 x값이 변한다)

y값은 year % N 로 나타낼 수 있다.

즉, year는 x부터 시작해 M씩 증가되고 그 때 year % N == y 일 때의 year값을 찾으면 되는 것이다.

처음부터 끝까지 탐색하는게 아니라 x가 고정일 때 y값만 탐색해 시간복잡도를 줄인다. 

 

 

 

이 때 주의해야할 점은, 

12년 <2, 12>

이런 경우에는 year % 12(N) 를 하면 y값이 12가 아니라 0이 되어버린다.

이를 방지하기 위해 초기에 x와 y에 1을 빼주고,  

year % N == y 일 때 year에 1을 더해준다. 

 

 

마지막으로 <M:N>이 종말의 해이므로 year는 M과 N의 최소공배수까지 돌 수 있다. 

M * N보다 작은 M과 N의 최소공배수가 있을 수 있지만 그냥 M*N 까지 돌려도 통과가 됐다.