[99클럽 코테 스터디 TIL 21일차 / 백준 1003] 피보나치 함수 (Python)

 

문제를 읽고 처음에는 별 생각 없이 queue를 사용하여 코드를 작성하였다.

 

첫 코드

from collections import deque
t = int(input())

for _ in range(t):
    n = int(input())

    queue = deque([n])
    cnt0 = 0
    cnt1 = 0
    while queue:
        curr_n = queue.popleft()
        if curr_n == 0: cnt0 += 1
        elif curr_n == 1: cnt1 += 1
        else:
            a = curr_n - 2
            b = curr_n - 1
            queue.append(a)
            queue.append(b)

    print(cnt0, cnt1)

 

사실 이 코드는 문제에서 제시한 재귀함수를 BFS로 구현한 것 뿐이다.

구현 자체에는 문제가 없지만 6퍼에서 계속 시간초과가 발생하였다...

그러던 중에 이 문제가 DP로 푸는 문제라는 것을 알게되었고 한 번 계산 한 결과를 메모리에 저장하고 같은 문제 결과값을 원할때 바로 값을 가져올 수 있는 메모이제이션에 대해 알게 되었다.

 

메모이제이션을 활용하면 중복되는 계산과정을 할 필요가 없어지기 때문에 훨씬 시간 단축이 될 것이라는 판단이 되었다.

 

또한 3의 0의 개수는 2, 3의 0의 개수 합과 같고, 4의 0의 개수는 2, 3의 0 개수 합과 같다. 이렇게 0 또는 1의 개수도 피보나치가 적용이 된다.

 

최종 코드

from collections import deque
t = int(input())
arr0 = [-1 for _ in range(41)]
arr1 = [-1 for _ in range(41)]

arr0[0] = 1
arr1[0] = 0
arr0[1] = 0
arr1[1] = 1

idx = 2
for _ in range(t):
    n = int(input())
    while arr0[n] == -1:
        arr0[idx] = arr0[idx - 2] + arr0[idx - 1]
        arr1[idx] = arr1[idx - 2] + arr1[idx - 1]

        idx += 1
    print(arr0[n], arr1[n])

 

1. 0, 1 개수 계산 결과 값을 저장할 수 있는 배열 arr0, arr1을 만들어준다.

2. 피보나치 함수 값이 0, 1일때이 배열 arr0, arr1 값을 저장해준다.

3. 입력받은 n값의 계산 결과의 값이 아직 배열 arr0, arr1에 저장되어 있지 않은 경우

4. Bottom-up 방식을 사용해 n일때 0, 1개수 값을 구할때까지 반복한다.

5. 과정에서 나오는 계산 값은 계속하여 arr0, arr1에 업데이트 한다.

6. 입력받은 n값의 계산 결과의  값이 이미 배열 arr0, arr1에 저장되어 있는 경우

7. 바로 arr0[n], arr1[n] 값을 출력

 

위와 같은 알고리즘으로 코드를 작성하였다.

 

https://www.acmicpc.net/submit/1003/90199218