★피보나치수열 복습 필요_[python_파이썬_Pass]백준_9625번_BABBA_다이나믹프로그래밍_풀이

공부하는허딩크 : https://www.youtube.com/live/phXWvbSXQQk?feature=shared

1. 총 시간 : 40분

2. 이것저것 고민을 많이 하다가 피보나치수열의 방식을 활용하는 것을 찾아냈다. 하지만 피보나치 수열이 기억이 안난다..

"""

<규칙>

0 A

1 B    

2 BA

3 BAB

4 BABBA

5 BABBABAB

6 BABBABABBABBA

7 BABBABABBABBABABBABAB

k의 값 : 0, 1, 2, 3, 4, 5, 6,  7,  8  

전체   : 1, 1, 2, 3, 5, 8, 13, 20, 21

    A  : 1, 0, 1, 1, 2, 3, 5, 8

    B  :    1, 1, 2, 3, 5, 8

"""

 

<첫번째 시도 : 시간초과>

당연히 시간 초과를 예상했다. 답은 나오지만 너무 비효율 적인 코드였다.

K = int(input())

answer = "A"

for _ in range(1, K + 1):

    temp = ""

    for j in answer:

        if j == "A":

            temp += "B"

        else:

            temp += "BA"

    answer = temp

A , B = 0, 0

for i in answer:

    if i == "A":

        A += 1

    else:

        B += 1

print(A, B, sep = ' ')

 

<두번째 시도 : 맞았습니다.>

피보나치를 대충 검색해서 방법을 찾아보고 다시 코드를 작성했다.

import sys

input = sys.stdin.readline

K = int(input())

# 40분 걸림 : 피보나치 수열 복습 필요

#피보나치수열

def fibo(k):

    a, b = 0, 1

    if k == 1:

        return a, b

   

    for i in range(1, k ):

        a, b = b, a + b

    return a, b

print(*fibo(K))

               

 

나중에 아래의 내용 참고해서 피보나치수열을 다시 복습해보자.

https://richwind.co.kr/3

피보나치(Fibonacci) 수열을 구현하는 7가지 방법 - 파이썬(Python) 피보나치 구현 7선