이 글을 쓰게된 이유
처음에는 완전 탐색으로 풀었다가 시간 초과가 나서..
조금 더 고민해 보다가 답이 나오지 않아 검색을 해서 답을 찾아봤는데..
이해가 가는 블로그 글이 하나도 없다.. 적어도 나같은 바보들도 이해갈 수 있게 설명을 써놓은 블로그는 없었다…
그 뭐야.. 한 블로그에서는 풀이에 왼쪽에 주어진 연도를 M으로 나누었을 때 x이어야 하기 때문에.. 라고 적혀있는데 그걸 아는 사람들은 문제 이미 정답을 제출하고 구글에 이 문제를 검색해서 풀이를 보러 들어오지 않았을 것이다.
그래서 나는 문제를 풀지 못한 사람들도 이해할 수 있는 풀이를 남기려고 해본다.. 나 같은 경우엔 이미 답을 아는 상태에서 풀이를 해석해 보았다.
풀이 시작
M, N, x, y가 입력으로 들어온다.
여기서 x는 x + i*M번째마다 등장하고 y는 y+j*N번째마다 등장한다. 이 부분은 다들 이해가 갈 거라 생각한다.
그리고 종말의 날은 M, N의 최소공배수이다.
이건 또 왜냐? 종말의 날은 x=M, y=N인 경우이기 때문에 x = M + i*M번째마다, y = N + j*N번째마다 등장.
즉, x = (1+i)*M y = (1+j)*N 번째마다 등장하기 때문에 두 값이 같을 때는 M과 N의 최소공배수이기 때문이다.
1
2
3
4
5
6
7
8
예시)
M = 10, N = 12
x = 10, y = 12 일 때
x가 10인 날은 => 10, 20, 30, 40, 50, 60, ...
y가 12인 날은 => 12, 24, 36, 48, 60, ...
이므로 종말년도는 두 값의 최소공배수이다.
=> "아 뭔가 루프를 돌 때 종말년도인 M, N의 최소공배수는 넘지 말아야겠구나!"
자 그러면 이제 답을 구해보자.
M, N, x, y가 입력으로 들어왔고 우리는 <x:y>가 몇번째 날인지 알고 싶다.
위에서 말했듯이 X = x + i*M, Y = y + j*N번째 날에 등장하고 우리가 원하는 것은 두 숫자가 동시에 등장하는 날 즉, X == Y가 되는 날이다.
따라서 x + i*M = y + j*N이 되고 이 식에서 y를 이항해주면
1
x + i*M - y = j * N
위 식을 유도해낼 수 있다.
그렇다 위 식이 바로 답이다.
우리는 x에 M을 계속 더해준 값에 y를 뺀 값이 N의 배수인 가장 작은 수를 구해주면 되는 것이다.
이를 코드로 나타내면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
doomsDay = lcm(M, N) # 종말의 날 = M, N의 최소공배수
answer = -1
while x <= doomsDay:
# (x + i*M - y)의 값이 N으로 나누어지는 경우 그 날이 답이며 루프 탈출
if (x - y) % N == 0:
answer = x
break
x += M # 루프를 한번 돌 때마다 x에 M을 더해줌
if answer == -1:
# 루프를 다 돌았는데 답을 구하지 못한경우 = 종말의 날까지 존재하지 않는 날.
print(-1)
else:
print(answer)
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def gcd(x, y):
while(y):
x, y = y, x%y
return x
def lcm(x, y):
result = (x*y)//gcd(x, y)
return result
n = int(input())
for _ in range(n):
M, N, x, y = map(int, sys.stdin.readline().split())
answer = -1
doomsDay = lcm(M, N)
while x <= doomsDay:
if (x - y) % N == 0:
answer = x
break
x += M
if answer == -1:
print(-1)
else:
print(answer)