8월 11일 금요일 코테

 

No. 1

 

 

-  문제 : subproblem을 그대로 합치면 되는 DP / 피보나치 수

https://www.codetree.ai/missions/2/problems/fibonacci-number?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

코드 

 

# 1. 문제정의 
# 2. 가장 작은 문제풀기 
# 3. 점화식으로 표현 

N= int(input()) # 마지막 번째 수 

#1. 문제정의 
F = [0 for _ in range(N+1)] # N개의 피보나치 수들이 저장된 리스트 

#2. 가장 작은 문제 풀기 

F[1]= 1
if N >=2:
    F[2] = 1 

# 3. 관계식 표현 
if N >=3: # N 값 범위 주의... 
    for i in range(3,N+1):
        F[i] = F[i-1] + F[i-2]

print(F[N]) #중괄호 써야됨에 주의...

예시

새롭게 알게된것 

 

DP 문제가 이렇게 쉽게 풀리다니... 

 

* 초깃값을 문제에 제시된거 다 적어도된다. 

* 배열 정의시 , 문제에 주어진 N 값의 범위만큼 원소를 만들어 두면 for 문에는 범위 조건 따로 안적어도 된다... 

 

 

주의할점

 

내풀이) N값의 범위에 주의... 1,2,3 일때 .. 주의.. 

 

문제정의 부분은 i 번째 오는 값에 대한 설명을 말로 써주는것임.