[BOJ][⚪1][백준#06064] 카잉 달력

문제 출처

BAEKJOON Online Judge #6064

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.  예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.  네 개의 정수 M, N, x와 y가 주어질 때, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 가 k번째 해를 나타내는 것을 의미한다. 만일 에 의해 표현되는 해가 없다면, 즉, 가 유효하지 않은 표현이면, -1을 출력한다.

예제

입력

3
10 12 3 9
10 12 7 2
13 11 5 6

출력

33
-1
83

My Sol

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    M, N, x, y = map(int, input().split())

    set1 = set(range(x, M*N+1, M))
    set2 = set(range(y, M*N+1, N))
    set3 = set1 & set2

    if not set3:
        print(-1)
        continue
    print(min(set3))

set의 연산을 활용하였다. M으로 나누었을 때 x가 나오는 원소의 집합을 set1, N으로 나누었을 때 y가 나오는 원소의 집합을 set2로 지정하고, 이 집합의 교집합을 구하였다. 이 교집합을 set3라고 하는데, 이 교집합이 비어있다면 M:N이 될 때까지도 해당하는 x, y 쌍을 찾을 수 없으므로 -1을 출력하는 것이고, 만약 교집합이 있다면 이 교집합의 원소 중 가장 작은 값이 최초의 를 만족하는 값이 될 것이다. 이를 찾아 출력해준다.

결과

맞았습니다!!

모범답안

출처

from math import lcm
import sys
        
T = int(input())
for _ in range(T):
    M, N, x, y = map(int, sys.stdin.readline().split())
    limit = lcm(M, N)
    
    while x <= limit:
        if (x - y) % N == 0:
            print(x)
            break
        x += M
    else:
        print(-1)

코드도 짧고, 연산시간도 효과적인 풀이가 있어 분석해보려 한다. 발상의 전환이었다. x를 M만큼 더하면서 매번 N으로 나눈 나머지가 0이라면 x:y를 만족하는 것이므로 이 때의 x를 출력하고, 만약 한계까지 갔음에도 불구하고 이를 만족하는 x y가 없다면 -1을 출력한다.

이때 한계를 정해주는 것이 획기적이었는데, math 모듈의 lcm 함수를 사용하는 점이었다. lcm 함수는 least common multiple의 약자로, 두 수의 최소공배수를 구하는 함수이다. 즉, 최소공배수까지 x가 커졌음에도 식을 만족하는 x y가 없다면 그 이후에도 없다는 뜻이다.