[백준/Python] 6064 카잉 달력

📌문제 탐색하기

• 카잉 제국 백성들은 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, N, x, y가 주어질 때, <x:y>는 몇 번째 해를 나타내는지 구하기

입력

• 입력 데이터의 수를 나타내는 정수 T (크기 명시되어 있지 않음)
• 각 테스트케이스에 네 개의 정수 M, N, x, y가 주어짐 (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N)

출력

• 각 테스트 데이터에 대해 <x:y>가 몇 번째 해인지 나타내는 정수 k 출력
• <x:y>가 유효하지 않은 표현이라면 -1 출력

풀이 방법 생각해보기

 

위 예제와 같이 M, N이 주어졌을 때 표현할 수 있는 모든 해의 개수는 M과 N의 최소공배수와 같다는 것을 알 수 있다.

 

또한 <x:y>가 주어지면 <x:a> 다음으로 <x:?> 형태가 되는 해가 무슨 해인지 a에 M을 더해 구할 수 있다. 만약 (a+M)이 N보다 작거나 같다면 <x:y>의 다음 해는 <x:a+M>이 된다. 만약 (a+M)이 N보다 크다면 (a+M)%N이 0이라면 <x:1>, 아니라면 <x:(a+M)%N>이 된다. 이 점을 활용하여 모든 <x:?>에 대해 브루트포스 탐색하여 <x,y>를 찾아서, 최종적으로 몇 번째 해인지 구할 수 있다. 

 

📌코드 설계하기

1. 테스트케이스 개수 T를 입력받는다.
2. T번만큼 아래 과정을 반복한다.
   1. M, N, x, y를 입력받는다.
   2. 가능한 해의 형태 중 마지막으로 <x:?> 형태인 해를 구하기 위해 M과 N의 최소공배수를 구해 max_count에 할당한다.  
   3. 현재까지 확인한 해의 개수를 셀 변수 count를 x로 초기화한다.
   4. a를 x로 초기화한다.
   5. count가 max_count보다 작거나 같을 때까지 아래 과정을 반복한다.
      1. a가 N보다 크다면, (a%N)을 계산해서 0이라면 a에 N을 할당하고, 아니라면 a에 (a%N)을 할당한다.
      2. a와 y가 같다면 count를 출력하고 탐색을 종료한다.
      3. a와 y가 다르다면 a에 M을 더하고, count에 N을 더한다.
   6. 모든 탐색이 끝나도 일치하는 경우를 찾지 못했다면 -1를 출력한다.

 

📌정답 코드

Python

from math import gcd
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    M, N, x, y = map(int, input().split())
    
    max_count = M*N//gcd(M,N)
    
    count = x
    a = x

    while count <= max_count:
        a = (a-1)%N+1
            
        if a == y:
            print(count)
            break
            
        a += M
        count += M
    else:
        print(-1)

 

 

📌개선하기

위 코드로 AC를 받긴 했지만, 3920ms의 시간이 걸려 좀 더 효율적인 방법이 있을까 생각해봤다.

 

일단 기본적으로 내 코드에서 a는 x + kM 꼴로 증가하면서 매번 N으로 나눈 나머지를 적용하고 있다, 그리고 이 a가 y와 같아지는 순간을 찾는다. 하지만 매번 a에 대해 N으로 나눈 나머지를 구할 필요 없이 계속 count를 누적시키고 이 count를 바탕으로 y와 비교할 때만 나머지를 구해주면 된다. 즉, count와 a를 같은 변수로 관리할 수 있다.

 

이를 식으로 표현하면 (x + kM)%N==y가 되고, 이를 만족하는 k를 찾으면 된다. (x+kM)을 N으로 나눈 나머지가 y가 되는 순간을 찾는다는 것은, (x+kM-y)을 M으로 나눈 나머지가 0이 되는 순간을 찾는 것이다.

 

이를 적용하여 아래와 같이 코드를 개선할 수 있다.

from math import gcd
import sys
input = sys.stdin.readline

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

    max_count = M * N // gcd(M, N)
    count = x

    while count <= max_count:
        if (count - y) % N == 0:
            print(count)
            break
        count += M
    else:
        print(-1)

 

백준에 제출했을 때 기존 코드의 실행 시간인 3920ms에서 2300ms로 개선되었다.