동적계획1 백준

백준 2748 피보나치 2

import sys 

num = int(sys.stdin.readline())
#temp에 num개의 요소 일단 0으로
temp =[0 for _ in range(num+1)]
#0번째는 0, 1번째는 1로 세팅
temp[1] = 1

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

#N번째 출력
print(temp[-1])

피보나치 수열 1003

import sys 

def fibo(num) :
    zero = [1,0]
    one = [0,1]

    if num <= 1:
        return

    for i in range(2,num+1):
        zero.append(zero[i-1]+zero[i-2])
        one.append(one[i-1]+one[i-2])
       
    return zero, one

#문제 조건 범위 만들어 놓기
zero, one = fibo(40)

#N번째 출력
num = int(sys.stdin.readline())
for i in range(num):
    m = int(sys.stdin.readline())
    print("%d %d" % (zero[m], one[m]))

01 타일

import sys 

#뒤에 1 또는 00이 붙여진다.
#결국 temp[n] = temp[n - 1] + temp[n - 2]  
# n-1 번째에는 1을 붙이게 되고 n-2번째는 00를 붙이게 된다
def tile(n):
    answer = 0
    temp1 = 1
    temp2 = 2
    for i in range(1, n+1):
        if i == 1:
            answer = temp1
        elif i == 2:
            answer = temp2
        else:
            answer = temp1 + temp2
            temp1 = temp2 % 15746
            temp2 = answer % 15746
    
    print(answer % 15746)
        
tile(int(sys.stdin.readline()))

파도반 수열

import sys 

#1, 1, 1, 2, 2, 3, 4, 5, 7, 9
#결국 temp[n] = temp[n-2] + temp[n-3]  
#문제 조건  (1 ≤ N ≤ 100)
def pado(n):
    n-=1  #인덱스는 0부터 시작하니까
    temp = [1,1,1]
    if n<3: return temp[n]
    
    for i in range(3,n+1):
        temp.append(temp[i-2]+temp[i-3])
    
    return temp[-1]

n = int(sys.stdin.readline())
for _ in range(n):
    print(pado(int(sys.stdin.readline())))