글 읽기 - 파이썬) 시간초과 문제 질문드립니다

rkdr055 6년 전 0

각 숫자들을 리스트에 넣고 인접한 두 숫자들의 차의 gcd를 구하였습니다.

그 gcd들을 다시 리스트에 넣고 인접한 두 숫자들의 gcd를 구하였습니다.(갯수가 점점 줄어듭니다.)

계속 반복문을 돌려서 최종 gcd의 약수를 출력하는게 답이라고 생각하였습니다.

최종 gcd 값의 약수도 최대한 반복문이 적게 하여서 구하였고

프로그램을 돌리면 입력 즉시 답이 나오는데 왜 자꾸 시간초과가 뜨는걸까요?

import math
import sys
a=int(sys.stdin.readline())
list1=[int(sys.stdin.readline()) for i in range(a)]
list2=[]
list3=[]

def gcd(a,b):
    while(b != 0):
        if(a<b):
            (a,b)=(b,a)
        temp=a%b
        a=b
        b=temp
    return a

for j in range(len(list1)-1):
    list1[j]=list1[j+1]-list1[j]
del list1[len(list1)-1]

for k in range(len(list1)-1):
    for z in range(len(list1)-1):
        list2=list1
        A=list2[z]
        B=list2[z+1]
        list1[z]=gcd(A,B)
    del list1[len(list1)-1]

z=int(math.sqrt(list1[0]))
for i in range(1,z+1):
    if list1[0]%i==0:
        list3.append(i)
        list3.append(list1[0]//i)
del list3[0]
zip=set(list3)
list4=sorted(list(zip))
for z in range(len(list4)):
    print(list4[z],end=" ")

chogahui05 6년 전 2

이 TC에 대해서 답이 안 나오네요.

/*
3
145
652
361
*/

rkdr055 6년 전 1

와 진짜 오름차순 문제였네요

입력한 숫자들 오름차순 정렬해서 했더니 바로 해결됐습니다.

감사합니다

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

문제

문제

출처

ICPC

파이썬) 시간초과 문제 질문드립니다

rkdr055 6년 전 0

chogahui05 6년 전 2

rkdr055 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말