카잉 달력 [백준 6064] - python

import sys
input = sys.stdin.readline

def BOJ6064() :
  def getYear(M, N, x, y) :
    MAX_NUM = M * N
    
    while x <= MAX_NUM :
      if x % N == y % N:
        return x
      x += M
    return -1

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

BOJ6064()

 

접근 방법:

1. k를 정답인 숫자라 하자.

k - x 에 m을 나누면 나머지가 0이다.
k - y 에 n을 나누면 나머지가 0이다.

 

2. 정답의 최대 범위는 M,N의 최대공배수 이다.(최대공배수를 구하기 싫어 그냥 곱셈을 해주었다.)

답에 접근하는 법을 상세히 알아보자

 

정답을 M으로 나눈 나머지와 N으로 나눈 나머지는 같을 것이다. 1부터 값을 올리면서 접근한다면 최대 숫자가 16억 이므로 무조건 시간초과가 난다. 더 효율적인 방법이 없을까?

 

x를 N으로 나누고 M씩 더해주면서 답을 찾아가면 된다.

 

k - x 에 m을 나누면 나머지가 0이다.
k - y 에 n을 나누면 나머지가 0이다.

 

예를 들어 M = 10, N = 12, x = 3, y = 9 이다.

1) 3 % 12 != 9 % 12 

2) 13 % 12 != 9 % 12

3) 23 % 12 != 9 % 12 

4) 33 % 12 == 9 % 12 

 

 

장애물 이였던 것 :

1. 나머지를 이용해야 한다는 것 까지는 접근했지만 그 다음 단계 에서 상당히 막혔던 문제이다.

 

 

 

 

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

6064번: 카잉 달력