백준 6064번 카잉 달력

https://www.acmicpc.net/problem/6064
실패이유 : 시간초과

• 시간 초과 코드

import sys

t = int(input())

for _ in range(t):
    M, N, wanted_m, wanted_n = map(int, sys.stdin.readline().split())

    year = 1
    m = 1
    n = 1
    cycled = False

    while m != wanted_m or n != wanted_n:
        m += 1
        n += 1
        year += 1

        if m > M:
            m = 1

        if n > N:
            n = 1

        if m == 1 and n == 1:
            cycled = True
            break

    if cycled:
        print(-1)
    else:
        print(year)

• m 과 n 이 다시 <1, 1> 이 되면 한 cycle 을 돌았다고 판단해 반복문을 빠져나오도록 했음
• 그러나 m ,n 제한이 0 ~ 40000 이므로 모든 가능한 경우의 수는 16억임
  • 시간초과 발생 (O(M * N) 시간복잡도)

• 성공 코드

t = int(input())

for _ in range(t):
    maximum_m, maximum_n, wanted_m, wanted_n = map(int, input().split())

    wanted_m -= 1
    wanted_n -= 1           # 나머지 계산을 위해 1을 빼줌
    year = wanted_m         # m 을 고정

    cycled = True
    while year < maximum_m * maximum_n:     # n 만 바꿔가며 탐색, m*n은 공배수로 무조건 <1,1> 로 돌아온다.
        if year % maximum_n == wanted_n:
            print(year + 1)         # 나머지 계산을 위해 1을 빼줬으므로 1을 다시 더해줌
            cycled = False
            break
        year += maximum_m

    if cycled:
        print(-1)

• m 을 고정시키고 <m, ?> ? 에 해당하는 n값만 바꾼다.
  • O(M * N) ➔ O(N) 시간복잡도가 된다.
• M 과 N 의 곱은 공배수로 무조건 다시 <1, 1> 로 돌아온다.
• 나머지 계산 시 0 이 나올 수 있는데, 이는 달력에서 정의되지 않은 숫자이다.
  • 따라서 달력값들에 미리 1을 빼줘 0부터 정의할 수 있도록 한다.
  • 이후 원하는 값을 찾았다면 년수에 1을 다시 더해준다.

출처 : 코드플러스 - 알고리즘 기초 2/2 강의
https://code.plus/course/42