[python] 백준 6064 - 카잉 달력

출처 : 백준, https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

 

첫 번째 풀이 : 시간 초과

 

import math

def lcm(N, M):
  G = math.gcd(N, M)
  return M * N // G

if __name__ == '__main__':
  n = int(input())
  for _ in range(n):
    N, M, x, y = map(int, input().split())
    L = lcm(N, M)

    year = -1

    for i in range(L):
      if i % N == x - 1 and i % M == y - 1:
        year = i + 1
        break

    print(year)

 

날짜 계산 문제 떠올라서 하하 거렸더니 시간초과가 뜨네..........

 

 

두 번째 풀이 : 성공

 

import math

def lcm(N, M):
  G = math.gcd(N, M)
  return M * N // G

if __name__ == '__main__':
  n = int(input())
  for _ in range(n):
    N, M, x, y = map(int, input().split())
    L = lcm(N, M)

    if N < M :
      N, M = M, N
      x, y = y, x

    year = -1

    for i in range(x-1, L, N):#무조건 N이 큼
      if i % M == y - 1:
        year = i + 1
        break

    print(year)

 

뭐가 문제지하다가 굳이 모든 index를 다 살펴볼 필요가 없다는 것을 깨달았다.

나머지는 어짜피 반복되니까 M, N 중 큰 수만큼 증가하는 반복문을 돌리면서

M, N 중 작은 수에 대해서 나머지가 같음을 확인하면 된다.

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

나머지로 풀이하는 문제일 때 고려할 점.

 

1. 나머지의 범위는 0부터 시작하므로 범위를 맞춰주어야 반복 패턴의 사용이 가능하다.

2. 나머지는 나누는 수를 기준으로 반복되는 특성을 가지므로 반복문 사용 시 널뛰기가 가능하다.