[BOJ] [Python] 9625번 : BABBA

1) 규칙을 찾아보자

 

규칙 찾기

 

문제에 나온 예시를 그대로 적어보면,

F(n) = F(n - 1) + F(n - 2)  (n >= 2) 라는 규칙이 보인다.

 

즉, 피보나치 수열이다.

 

 

 

2) A와 B 관계를 보자

 

관계 찾기

 

n의 A 개수는 n-1의 B 개수이다. (n >= 1)

 

 

 

피보나치 수열을 재귀함수를 이용했을 때와는 달리, 리스트에 값을 저장하는 식[Memoization]으로 풀었다. 

 

num = int(input())

# 피보나치
# [0, 1, ... ]

dp = [0] * (num + 1)
dp[1] = 1

for i in range(2, num+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[num-1], dp[num])

 

 

 

+ 추가)

 

재귀함수를 이용한 피보나치 수열

 

재귀함수를 이용하면 했던 연산을 또 하게 된다.