글 읽기 - [파이썬] 시간 초과되는 원인을 모르겠습니다.

alsrl9 1년 전 0

M,N 중 작은 것을 기준으로 cycle을 돌고 그 사이클 안에 y가 있으면 그 순간 x의 값을 찾아 비교하는 코드를 작성했습니다.

제 예상으로 연산 횟수는 최대 40,000에 비교 연산 서너 개 더 들어가는 정도인데 python3으로 제출할 시 1%에서 시간 초과를 받습니다.

코드의 개선점이나 시간초과를 받을만한 사항이 있으면 알려주실 수 있으신가요?

import sys

T = int(sys.stdin.readline())
for _ in range(T):
    M, N, x, y = map(int, sys.stdin.readline().split())
    if M == N:
        if x == y:
            print(x)
        else:
            print(-1)
    else:
        if N < M:
            M, N = N, M
            x, y = y, x
        cycle = 0
        answer = -1
        while cycle < N:
            l, r = (cycle * M + 1) % N, ((cycle + 1) * M) % N
            if l <= y:
                if y - l + 1 == x:
                    answer = cycle * M + (y - l) + 1
                    break
            else:
                if N - l + y + 1 == x:
                    answer = cycle * M + (N - l + y) + 1
                    break
            cycle += 1

        print(answer)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 시간 초과되는 원인을 모르겠습니다.

alsrl9 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말