백준_6064_카잉달력

백준 6064번, 카잉달력 문제입니다

#시간제한 #수학

 

---

문제

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

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력

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

출력

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

문제 해석하기

매 줄마다 숫자가 하나씩 주어진다. <x:y>가 몇번째 해인지 구하는 문제이다. 예시 숫자를 넣어서 이해해보자
M=10, N=12인 경우를 넣어보자.

k=1 <1:1>
k=2 <2:2>
k=3 <3:3>
...
k=10 <10:10>
k=11 <1:11>
k=12 <1:12>
k=13 <1:13>
... 

이런 식으로 진행되어서 60번째 해가 마지막이다. 문제 이해가 끝났으니 해결책을 찾아보자

해결 방법 생각하기

1. 어떤 방법을 써볼까?

처음 생각한 방법은, 단순히 첫번째 해부터 1씩 반복문을 돌면서 x<M이면 x' = x+1이고 그렇지 않으면 x'=1이고, y<N이면 y'=y+1이고 그렇지 않으면 y'=1이라는 문제에서 주어진 규칙을 따라 계산해가면서 <x:y>와 일치하면 해당 k값을 return하고 k가 마지막 해가 되도록 일치하는 k가 나오지 않으면 -1을 리턴하는 방법이다. 또는, 위 조건을 해석하면 k%M+1 == x 이면서 k%N+1 == y 이라는 나머지를 활용한 식을 뽑아낼 수 있으니, 이를 이용해 k를 1씩 더해가면서 일치하는 k가 나올 때 까지 구하는 것도 괜찮아 보인다. 물론 이렇게 해결하는 방법이 가장 간단히 구현할 수 있을 것 같지만, 이렇게 풀면 시간초과가 나온다!

 

시간을 생각해서 k를 1씩 더해가면서 찾는 것이 아니라, 규칙을 찾아 식을 세우는 편이 좋아보인다.

2. 규칙 찾기

어떻게 시간을 줄일 수 있을까? 예시를 활용해서 계산을 해보자.

M=10, N=12, x=3, y=9인 경우를 넣어보자. 우리는 x=3, y=9인 k를 찾아야한다.

몇번째 해에 x=3일까?
: 3, 13, 23, 33, 43, ..., 3+i*10

몇번째 해에 y=9일까?
: 9, 21, 33, ..., 9+j*10

"k = x+ M의배수 = y+ N의배수" 임을 알 수 있다. 식으로 표현하면 k = x+iM = y+jN 이라고 하면 되겠다. i, j는 알 수 없으니까 i, j가 없는 식으로 변환해보자. 

k = x + iM --------------- ① 
→ k-x = iM  ------------- ② k-x는 M의 배수임을 알 수 있다.
→ (k-x)%M == 0 ------ ③ 이를 if문을 위한 조건식으로 바꾼다.

y도 마찬가지로 하면, 우리는 (k-x)%M==0 이고 (k-y)%N==0  인 k를 return하면 된다.

 

3. 최종 설계

1. 조건을 만족하는 k가 있으면 답은 k

2. 1을 반복하되, k가 마지막 해가 넘어도 끝나지 않으면 답은 -1

 

마지막 해는 언제일까? (반복문의 종료조건)

k가 마지막해를 넘기도록 일치하는 <x:y>가 없으면 -1을 출력해야한다. 언제가 마지막해일까? 문제에서 <M:N>이 마지막해라고 주어졌다. <M:N>이 되려면 k는 M,N의 최소공배수이다. 왜인지 잘 모르겠다면 예시를 넣어서 생각해보자. 아까 M=10, N=12인 예시에서 마지막해는 60번째 해라고 문제에서 설명해주었다. 60은 10과 12의 최소공배수이다. 그래서 종료조건은 k가 M,N의 최소공배수가 되면 반복문이 종료되게 하면 될 것 같지만 최소공배수도 구해야한다니... 최소공배수도 재귀함수로 구하면 시간이 좀 많이 걸릴 거 같다. 왜 이런 말을 했냐면, 그럴필요가 없어서이다

어차피 답이 없을거면 최소공배수를 넘겨도 답이 없다. 대충 넉넉하게 M*N까지로 종료시켜줘도 된다. M,N이 2,7이라면 14 = 2*7이 최대이다. 10,12처럼 2로 나누어떨어지니 2*5*6 = 60이지만, 아무튼 반복 최대치는 M*N으로 잡아도 된다는 걸 엿볼 수 있다.

 

구현하기

최종 코드

import sys
input = sys.stdin.readline

def solve(M,N,x,y):
    k = x
    while k <= M*N: # 대충 넉넉하게 M*N번
        if (k-x)%M==0 and (k-y)%N==0:
            return k
        k+=M
    return -1

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

 

 

(추가) 최소공배수로 잡으면?

import sys
input = sys.stdin.readline

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b, a%b)
 
def solve(M,N,x,y):
    k = x
    while k <= (M*N//gcd(M,N)): # 최소공배수이긴한데, 대충 M*N번
        if (k-x)%M==0 and (k-y)%N==0:
            return k
        k+=M
    return -1

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

M*N으로 잡았을 경우

최소공배수로 잡았을 경우. 확실히 메모리 많이 먹는다. M*N으로 쓰자

 

---

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

17425번: 약수의 합