1123_ TIL

2021.11.23

1003

# 1003
def one(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return one(x-1)+one(x-2)

def zero(x):
    if x == 0:
        return 1
    elif x == 1:
        return 0
    else:
        return zero(x-1)+zero(x-2)

T = int(input())
for i in range(T):
    N = int(input())
    print(zero(N),one(N), end = ' ')

피보나치수열 함수를 이용해서 풀어보려고 했더니 시간 초과가 뜬다.

DP를 이용해서 풀어야 한다고 해서 밑에 코드를 짜봤다.

이미 계산했던 것들을 리스트에 넣어주고 다음에 그 값을 구할 때

다시 계산하는 게 아니라 리스트에서 불러오면 돼서 시간적으로 단축 가능하다.

# 1003
T = int(input())
Z = [0,1,2,3]
for i in range(T):
    N = int(input())
    if N == 0:
        print(1,0)
    elif N == 1:
        print(0,1)
    elif N == 2:
        print(1,1)
    else:
        try:
            print(Z[N-2],Z[N-1])
        except:
            for i in range(Z.index(Z[-1]),N):
                Z.append(Z[i-1]+Z[i])
            print(Z[N-2],Z[N-1])