[백준 6064번] 카잉 달력 - python

문제 링크

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

6064번: 카잉 달력

풀이

- while문 사용해서 주어진 x,y값과 같아질 때까지 반복 : 시간초과 

# 시간초과 
t = int(input())

for _ in range(t):
  m, n, x, y = map(int,input().split())
  a = 1 
  b = 1 
  cnt = 0 
  result = True
  
  while True :
    cnt += 1 
    
    if a == x and b == y:
      break

    if a == m and b == n:
      print(-1)
      result = False
      break
      
    if a < m :
      a += 1 
    else:
      a = 1

    if b < n:
      b += 1 
    else:
      b = 1 

  if result : print(cnt)

- x에 m을 계속 더해나간 값  = y에 n을 계속 더해나간 값 일 때 정답 

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

x가 3인 해 3번째 ,13번째, 23번째, 33번째 ... 

y가 9인 해 9번째, 21번째, 33번째 ... 

 

k 를 정답이라고 하면 

( k - x ) % m =  0 이고 ( k - y ) % n = 0 을 만족시키는 k 값이 정답이다. 

이 때 k는 x에 m을 반복적으로 더하고, y에 n을 반복적으로 더한 값 중 하나이다. 

따라서 x에 m 만큼 반복적으로 더한 숫자 중 하나가 k이므로 해당 값이 ( k - y ) % n = 0 를 만족시키면 된다. 

t = int(input())

for _ in range(t):
  m, n, x, y = map(int,input().split())

  result = True
  
  while x <= m * n :
    if (x-y) % n == 0:
      print(x)
      result = False
      break
    x += m

  if result : 
    print(-1)