접근
문제를 읽어보면
년도를 나타내는 방식이 <x:y>라고 하였을 때 M,N이 주어진다.
M=10, N=12라고 가정했을 때
첫해는 <1:1>로 시작한다.
두번째 해는 <1+1:1+1> -> <2:2>
.
.
.
가다가
<10:10>
<1:11>
<2:12>
<3:1>
이렇게 나아간다.
즉 x<M이면 다음 년도인 x'는 x'=x+1이지만 아니라면 x'=1이 된다.
y도 똑같은 방식으로 계산된다.
<M:N>은 그들 달력의 마지막 해이다.
즉 이 해에 도달하려면 최소공배수번째의 해에 도달했다는 것을 의미한다.
여기서 구하고자 하는 것은
M,N,x,y가 주어졌을 때 x,y가 나타내는 해가 몇번째 해에 해당되는가를 구해야 한다.
또한 한가지 더 조건이 있는데 그 해당하는 <x:y>가 없으면 -1를 출력해야 한다.
이는 M,N의 최소공배수의 해를 포함한 그 이전에 저 수가 없을 때 -1을 출력하는 것으로 해결한다.
(왜 최소공배수인가?
M=10,N=12로 가정했을 때 최소공배수는 60
60번째는 <10,12>이면 61번째는 <1:1>이다
즉 다시 처음으로 돌아간다.
그러니까 최소공배수 년도 이전에 등장하지 않는다는 것은 그 이후로도 영원히 등장하지 않는 년도라는 것이다.)
몇가지 접근법이 있다.
첫번째 접근법은 시간초과가 발생하고
두번째 접근법은 시간초과가 발생되지 않는다.
풀이과정 1
먼저 첫번째 접근법은
1부터 시작해서 1씩 더해가면 최소공배수까지 가는 것이다.
즉 해를 하나씩 더해가면서 그 해를 M과 N으로 나눈 나머지가 x,y와 일치하는가를 구하는 것이다.
하지만 그 해가 M과 N으로 나눠지는 경우 나머지는 0이 된다. 나머지가 0이 된다는 것은 그 해에 x'또는 y'가 각각 x'=M, y'=N이라는 것이다.
따라서 풀이는 아래와 같다.
import java.util.*;
import java.io.*;
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));
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());
int y = Integer.parseInt(st.nextToken());
int end=0;
if(M>N) end =M*N/gcd(M,N);
else end = M*N/gcd(N,M);
int answer =0;
for(int i=1;i<=end;i++){
int f_x=0;
int f_y=0;
if(i%M!=0){
f_x = i%M;
}
if(i%N!=0){
f_y=i%N;
}
if(i%M==0){
f_x=M;
}
if(i%N==0){
f_y=N;
}
if(f_x==x && f_y==y){
answer = i;
break;
}
}
if(answer!=0) bw.write(Integer.toString(answer));
else bw.write("-1");
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
static int gcd(int A, int B){
if(B==0) return A;
return gcd(B,A%B);
}
}하지만 시간초과가 발생한다.
저렇게 1씩 더해가는 방식이 잘못된 것이다. 운이 좋지 않으면 최소공배수 끝까지 가야 한다.
풀이과정 2
따라서 발견한 두번째 방법은 내가 스스로 생각해본것은 아니고 누군가의 풀이를 참고한 것이다.
여기서의 접근법은
x를 중심으로 할 것인지 y를 중심으로 접근할 것인지 먼저 결정한다.
난 x를 중심으로 하는 풀이를 하겠다.
M*n+x는 결국 구하고자 하는 x를 가지고 있는 해이다.
만약 x=3이고 M=10이라고
3번째,
13번째,
23번째는
<3:?>
의 형태를 가지고 있는 것이다.
여기 Mn+x에서 y를 뺀 Mn+x-y가 N으로 나누어진다면
이 M*n+x년도는 우리가 구하고자 하는 x와 y로 표현되는 해라는 것이다.
그 이유는 아래를 보면서 설명한다.
첫해는 <1:1>로 시작한다.
두번째 해는 <2:2>
.
.
.
가다가
<10:10>
<1:11>
<2:12>
<3:1>
보면 x는 M마다 바뀌고 y는 N마다 바뀐다.
서로 다르게 나아가기 때문에 우리는 어려워 하는 것이다.
그러면 <3:4>의 의미는 10을 몇번 곱하고 거기에 3을 더한것이고
12를 몇번 곱하고 거기에 4를 더한 것이기 때문에 결국 저 해당 년도에 4를 뺀다는 것은 12로 나눠진다는 것이다.
따라서 아래와 같이 풀이한다.
import java.util.*;
import java.io.*;
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));
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());
int y = Integer.parseInt(st.nextToken());
int end=0;
if(M>N) end =M*N/gcd(M,N);
else end = M*N/gcd(N,M);
int n=0;
int answer =0;
while(M*n+x<=end){
if((M*n+x-y)%N==0){
answer= M*n+x;
break;
}
n++;
}
if(answer!=0) bw.write(Integer.toString(answer));
else bw.write("-1");
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
static int gcd(int A, int B){
if(A%B==0) return B;
return gcd(B,A%B);
}
}
