알고리즘 스터디 ( dp 에 대해 1주 연장 )

( dp 에 대해 1주 연장 )

사유: dp 난이도, 기초 문제 추가 학습

 

 

백준: 2748 python

# 점화식 풀이
n = int(input())
dp = [0] * 91


dp[0] = 0
dp[1] = 1;

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

print(dp[n])


# 재귀 함수 풀이
# but.. 메모리.. 초과..
n = int(input())


def fib(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

print(fib(n))

 

백준: 1463 python

n = int(input())
dp = [0] * 1000001

dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 1

for i in range(4,n+1):
    dp[i] = dp[i-1]+1

    if i%2 == 0:
        dp[i] = min(dp[i], dp[n//2] +1)
    if i%3 == 0:
        dp[i] = min(dp[i], dp[n//3] +1)

print(dp[n])

백준: 9095 python

t = int(input())

dp = [0] * 11

dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 4

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

for i in range(0,t):
    n = int(input())
    print(dp[n])