boj 1003 피보나치 함수 (python)

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

진짜 어렵지 않아보였는데 꽤나 애먹은 문제 ^,ㅠ
이 문제는 DP로 풀어야 하는데 처음에 메모이제이션으로 접근했다가 자꾸 NameError가 뜨면서 문제 원인을 알 수 없게됨

그래서 타뷸레이션 방식으로 바꿨다.

타뷸레이션 방식이 메모이제이션보다 더 효율적이기도 하고? (재귀를 쓰다보면 콜스택에 함수가 쌓이면서 메모리를 낭비하는 문제가 있는 반면에 타뷸레이션으로 하면 재귀를 쓰지 않고 상향식으로 접근하면서 계속 했던 값을 저장하니 메모리도 더 효율적으로 쓰는 장점이 있다. )

 

정답 풀이

input = open(0).readline

def fibonacci_one(n):
    global table
    if n < 2: 
        return n

    for i in range(2, n + 1):
        table[i] = table[i-2] + table[i-1]

    return table[n]

def fibonacci_zero(n):
    global table_zero
    if n == 0: 
        return 1
    elif n == 1:
        return 0

    for i in range(2, n + 1):
        table_zero[i] = table_zero[i-2] + table_zero[i-1]

    return table_zero[n]

if __name__ == '__main__':
    table = [0 for _ in range(41)] 
    table[0], table[1] = 0, 1

    table_zero = [0 for _ in range(41)]
    table_zero[0], table_zero[1] = 1, 0

    for i in range(int(input())):
        N = int(input())
        print(fibonacci_zero(N), end= " ")
        print(fibonacci_one(N))

• table과 table_zero의 값을 41개로 한건 테스트 케이스 N이 0~40 이기 때문에 41개로 한 것
  -> (40개로 맞췄다가 IndexError를 만남.. N이 40인 경우를 메모할 공간이 없으니께 그렇죠)
• 굳이 0을 구하는 경우와 1을 구하는 경우 두 가지로 나누지 않고도 다른 방법이 있겠지만.. 일단은 이게 더 직관적이게 보여서 이런 방식으로 풀었다.
• 나중에 좀더 숏코딩을 할 수 없을지 확인해봐야할듯

---

 

 

 

문제의 메모이제이션 풀이 방식.. (이건 제출하면 틀립니다..)

input = open(0).readline

sys.setrecursionlimit(10000)

def fibonacci_one(n, memo):
    if n == 0: 
        return 0
    elif n == 1:
        return 1

    if(memo.get(n) == None):
        memo[n] = fibonacci_one(n-2, memo) + fibonacci_one(n-1, memo)

    return memo[n]

def fibonacci_zero(n, memo):
    if n == 0: 
        return 1
    elif n == 1:
        return 0

    if(memo.get(n) == None):
        memo[n] = fibonacci_zero(n-2, memo) + fibonacci_zero(n-1, memo)

    return memo[n]

if __name__ == '__main__':
    zero_dp = {0:1, 1:0}
    one_dp = {0:0, 1:1}

    for i in range(int(input())):
        N = int(input())
        print(fibonacci_zero(N, zero_dp), end=" ")
        print(fibonacci_one(N, one_dp))

• NameError가 자꾸 발생함.
  -> 이런 경우 선언되지 않은 변수를 사용하는 경우라는데 아무리 봐도 여기서 선언하지 않은 변수를 사용하는 경우가 언제인지 모르겠다.
• 뭐가 틀렸는지 알고싶은데 아시는 분 알려주심 감사하겠습니다 ^,ㅠ