백준 - 파도반 수열(파이썬)

📃 문제

💟 코드

시간 제한와 메모리를 고려하지 않고 풀었을 때에는 빠르게 풀었지만, 시간 제한과 메모리를 고려하며 시간이 조금 걸렸다.

첫번째 시도

# 백준 9461 파도반 수열

T = int(input())
for t in range(T):
    N = int(input())
    lst = [1, 1, 1]
    while len(lst) != N:
        next_thing = len(lst) - 1
        lst.append(lst[next_thing - 2] + lst[next_thing - 1])
    print(lst[-1])

메모리를 고려하지 않아, 메모리 초과가 생겼다. append를 활용해서 그런것 같았다..ㅠㅠ

두번째 시도

# 백준 9461 파도반 수열

T = int(input())
for t in range(T):
    N = int(input())
    lst = [1, 1, 1]
    cnt = 3
    while cnt != N:
        a = lst.pop(0)
        b = lst[0]
        lst.append(a+b)
        cnt += 1
    print(lst[-1])

이번엔 시간 초과로 실패했다.. pop과 append를 같이 활용해서 그런것이 아닌가... 생각이 든다ㅋㅋㅋㅋㅋㅋ

세번째 시도(정답)

# 백준 9461 파도반 수열

T = int(input())
for t in range(T):
    N = int(input())
    lst = [1, 1, 1] + [0 for x in range(97)]
    cnt = 3
    while lst[N - 1] == 0:
        lst[cnt] = (lst[cnt - 3] + lst[cnt - 2])
        cnt += 1
    print(lst[N - 1])

✨ 코드 풀이

N이 100까지만 주어진다 했으니, lst 안에 1 3개를 넣어놓고 나머지는 0으로 97개를 채워놓았다.
이 수열의 특징이 나보다 3개 앞의 숫자와 2개 앞의 숫자를 더한 값이 결과값이 되므로, lst[cnt] = (lst[cnt - 3] + lst[cnt - 2])와 같이 코드를 작성하였다.
그리고 해당 값을 lst의 올바른 자리에 바꿔 끼워넣는 식으로 코드를 작성했더니 성공했다!