[백준/파이썬] 1003번

📍백준 1003번 문제

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

코드

import sys
input = sys.stdin.readline

test_case = int(input())

for _ in range(test_case):
    num = int(input())
    if num == 0:
        print("1 0")
        continue
    if num == 1:
        print("0 1")
        continue
        # 앞이 0, 뒤 1
    arr = [[1, 0], [0, 1]]
    for i in range(2, num+1):
        arr.append([arr[-1][0]+arr[-2][0], arr[-1][-1]+arr[-2][-1]])
    print(arr[-1][0], arr[-1][-1])

풀이

피보나치 수열과 마찬가지로 0과 1의 개수도 f(n) = f(n-1) + f(n-2)의 식으로 풀 수 있다.
이차원 배열에 값을 저장후, 마지막값(-1)과 그 전 값(-2)을 더해주면 된다.