글 읽기 - 시간 복잡도를 줄이고 싶습니다

yechan1031 1년 전 0

문제는 풀었지만 실행 속도가 너무 느립니다

어떻게 해야 빠르게 할 수 있나요?

nums = list(map(int ,input().split()))
i = 1
while True:
    c = 0
    i += 1
    for num in nums:
        if i % num == 0:
            c+=1
    if c >= 3:break
print(i)

ufshg 1년 전 1

500ms정도 나오시나요?

문제자체가 브루트포스 문제여서 다소 시간이 걸리는게 맞습니다. 시간이 줄어들진 모르겠지만 떠오르는 다른 방법으로는 5개중 3개씩 뽑는 조합수가 10개니까, 각각 최소공배수를 구하고 그중 최솟값을 찍는 방법도 있겠네요.

ufshg 1년 전 1

제 코드와 비교해봤을때 다른점은 시작값 i가 작성자분께선 1이라는 점입니다.

최소공배수를 구하는 문제니까 1부터 시작하기보단 배열 내 최솟값부터 시작하는게 조금은 더 효율적일겁니다!

yechan1031 1년 전 0

덕분에 72ms로 줄였어요 감사합니다

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

문제

문제

출처

ICPC

시간 복잡도를 줄이고 싶습니다

yechan1031 1년 전 0

ufshg 1년 전 1

ufshg 1년 전 1

yechan1031 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말