[백준][DP] 2193번 이친수 python (200919)

 

1. 문제 설명

 

 

2. 풀이 

 

def solution(num):
    two_num = bin(num)[2:]
    fibo_list = [1,1]
    for fib_idx in range(2,num):
        fibo_list.append(fibo_list[fib_idx-2] + fibo_list[fib_idx-1])
        
    if not fibo_list:
        return 0

    return fibo_list.pop()

num = int(input())
print(solution(num))

간단히  6 까지만 손으로 그려보면 

2 - 1개

3 - 2개

4 - 3개

5 - 5개

6 - 8개

7 - 5+8 = 13개 

앞의 두 수를 더해서 만들어 지는 것을 알 수 있다. 피보나치 

 

 

피보나치는 DP로 풀어야 한다. ! 

그래서 리스트에 각 값을 저장해주는 방식으로 풀었음 

 

 

3. 정리

DP 의 가장 기본적인 컨셉은  

분기 점이 있다는 거다

이전 계산 + 뭐시기 = 지금  대부분 이런 방식임

 

따라서 각 계산들을 리스트에 담아두는 방식으로 연산을 해야함

피보나치가 대표적 예시임