[백준] 1003. 피보나치 함수 / python 파이썬

🚩 동적프로그래밍(DP)

 

thinking

1. 시간초과 난 코드

피보나치 수열 코드와 동일하게 짜되, n == 0 or 1 인 경우 0과 1의 호출횟수를 카운트하도록 함수를 구성했다.

output은 맞게 나왔지만 시간초과 뜸

 

2. success 😀

0호출횟수와 1호출횟수를 리스트로 만들어 피보나치 수열처럼 n-1, n-2의 호출횟수를 더하는 방식으로 코드를 짬.

n = 8 인 경우, cnt_0 = [1, 0, 1, 1, 2, 3, 5, 8], cnt_1 = [0, 1, 1, 2, 3, 5, 8, 13]가 되어 n번째 원소를 출력하면 된다

 

코드 (pass)

T = int(input())
for tc in range(T):
    N = int(input())
    cnt_0 = [1, 0]  # 0 호출횟수 기록하는 리스트
    cnt_1 = [0, 1]  # 1 호출횟수 기록하는 리스트

    for i in range(2, N + 1):
        cnt_0.append(cnt_0[i - 1] + cnt_0[i - 2])  # 이전 두 단계의 0 호출횟수를 더함
        cnt_1.append(cnt_1[i - 1] + cnt_1[i - 2])

    print("{} {}".format(cnt_0[N], cnt_1[N]))

 

시간초과 난 코드 (fail)

def f(n):
    global cnt_0, cnt_1
    if n == 0:  # n이 0이면 0호출횟수 1 증가
        cnt_0 += 1
        return cnt_0, cnt_1
    elif n == 1:  # n이 1이면 1호출횟수 1 증가
        cnt_1 += 1
        return cnt_0, cnt_1
    else:
        return f(n-1) + f(n-2)


T = int(input())
for tc in range(T):
    N = int(input())
    cnt_0, cnt_1 = 0, 0
    f(N)
    print("{} {}".format(cnt_0, cnt_1))

 

 

한줄후기

시간초과 어쩔.. 맨날 시간초과 뜨고 나서야 코드 다시 짜는 인생..