[백준] 1003: 피보나치 함수

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

DP(Dynamic Programming)를 이용하여 풀었다.

import sys

input = sys.stdin.read
inputs = input().splitlines()

n = int(inputs[0])
cases = list(map(int, inputs[1:]))

fibo = [[0, 0] for _ in range(41)]
fibo[0] = [1, 0] 
fibo[1] = [0, 1]

for i in range(2, 41):
    fibo[i][0] = fibo[i - 1][0] + fibo[i - 2][0]
    fibo[i][1] = fibo[i - 1][1] + fibo[i - 2][1]

results = []

for n in cases:
    results.append(f"{fibo[n][0]} {fibo[n][1]}")

sys.stdout.write("\n".join(results) + "\n")

일단 문제만 봐서는 잘 모르고 직접 그려보면 알 수있는데, 0과 1도 피보나치 형식으로 개수가 나오기 때문에 이를 활용해야 한다.

0이 나오는 개수와 1이 나오는 개수를 살펴보면
규칙이 있다. (직접 해보셈 ㅇㅇ..)

어쨌든 피보나치임.

그래서 이 점화식을 구현해야된다.

아마도 해보지는 않았는데 재귀함수쓰면 안될꺼임.

똑똑한 우리는 DP를 사용해야한다. 근데 계산된 값을 재활용하여 써야됨.

1. 40개의 배열을 초기화.
2. fibo 0번째 초기화
3. fibo 1번째 초기화

0이랑 1번째를 안하면 노답이다. 이건 개초딩 데려와도 이거 할 듯.

그리고 반복문을 통해 40개의 배열(0,1을 빼고)을 완성시키는게 첫 번째 for문이다.

아래는 2부터 시작이니 i에 2를 넣은 것이다.
fibo[2][0] = fibo[1][0] + fibo[0][0]
fibo[2][1] = fibo[1][1] + fibo[0][1]

아래는 i에 3를 넣은 것이다.
fibo[3][0] = fibo[2][0] + fibo[1][0]
fibo[3][1] = fibo[2][1] + fibo[1][1]

이해가 간다.

나중에 다시 보면 이해 못할 수 있으니 다시 말하는데

[[x1][y1], [x2][y2], [x3][y3]... ]
이런식임

그니까 x3 = x1 + x2, y3 = y1 + y2임

그리고 마지막으로 cases에 담긴 걸 가져와서 for문을 돌린다. cases에 들어간 순서대로 n에 값이 들어가서 결과물을 내어준다.