글 읽기 - 시간초과뜹니다,, 초과가 뜨는 이유가 궁금합니다.

cherryshine 1년 전 0

또, 혹시나 반례가 있다면 알려주세요 ..ㅠ

T = int(input()) # 테스트 케이스 T 개수 입력받기
list_a = [] 
list_b = []

for i in range(T): #테스트케이스 개수만큼 반복 
    a, b = map(int, input().split()) #최소공배수를 구할 두 수를 입력받기 (테스트케이스 개수만큼)
    count = 0 # while문을 빠져나오기 위해 만든 변수
    k = 1 # a와 b에 1부터 차례대로 곱함. 

    while(count == 0): 
        list_a.insert(i,a*k) # a리스트의 i번째 인덱스에 a x k 담기
        if list_a[i] in list_b: # list_a의 i번째항이 list_b에 내포되어 있다면
            print(list_a[i]) # list_a의 i번째항 출력
            count = 1 # while문을 빠져나오고 다음 테스트케이스를 수행하기 위해 count=1로 초기화

        list_b.insert(i,b*k) # b리스트의 i번째 인덱스에 b x k 담기
        if list_b[i] in list_a: # list_b의 i번째항이 list_a에 내포되어 있다면
            print(list_b[i]) #list_b의 i번째항 출력
            count = 1 # while문을 빠져나오고 다음 테스트케이스를 수행하기 위해 count=1로 초기화
        k += 1 # a와 b에 곱해질 k 를 1씩 증가시키기

rhasya 1년 전 0

45000 44999

이렇게 큰 수를 넣어보면.. 20억 정도 나오는데..

최악의 경우 O(N^2) 이 되어 해결이 어려울 것 같네요..

더 빠른 방법을 고민해야 할겁니다..

(유클리드 호제법 같은..)

cherryshine 1년 전 0

시간복잡도는 완전 무지해서 ........

그냥 일단 돌아가게 해보자 ! 하는 마인드로 시작했거든요.

혹시 팁같은것 있으실까요 ..!

rhasya 1년 전 0

위에도 적었지만..

"유클리드 호제법" 을 공부해 보세요..

두 수의 최대공약수를 매우 빠르게 구할 수 있습니다.

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

문제

문제

출처

ICPC

시간초과뜹니다,, 초과가 뜨는 이유가 궁금합니다.

cherryshine 1년 전 0

rhasya 1년 전 0

cherryshine 1년 전 0

rhasya 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말