글 읽기 - 시간문제

lkyxbar 2년 전 0

일단 실행을 시켜봤습니다 그랬는데 엄청난 문제가 생겼습니다 바로 시간 문제였습니다 1000을 넣어도 오래걸립니다 대략 제가 계산한건 O(n)인데 이거도 뭔가 잘못 된것 같습니다 이렇게 쉽게 안 풀릴껄 알고있었지만 시간 복잡도 계산이 잘못된걸까요?

def fib(n):
    while True:
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            return fib(n-1)+fib(n-2)
N=int(input())
print(fib(N))

junseo 2년 전 1

https://www.acmicpc.net/blog/v...

dslr 2년 전 2

2747번이나 2748번이 그런 풀이법이고 이 문제는 괜히 골드가 아닙니다. 다른 방식으로 접근해야 됩니다.

mk9901 2년 전 2

분할 정복 키워드로 한번 접근해보세요.
피보나치에 대한 분할 정복은 이항 계수로 풀어 쓸 수 있다고 합니다.

lkyxbar 2년 전 0

다들 진짜 감사합니다

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

문제

문제

출처

ICPC

시간문제

lkyxbar 2년 전 0

junseo 2년 전 1

dslr 2년 전 2

mk9901 2년 전 2

lkyxbar 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말