BOJ 다이나믹 프로그래밍 1

🪄 파스칼의 삼각형

정수 n과 k가 주어졌을 때 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 출력하는 문제

점화식 세워보기

1. N번째 행에는 N개의 수가 있다. → pascal = [[1 for _ in range(i)] for i in range(1, 31)]
2. 첫 번째 행은 1이다. → for i in range(2, n):
3. 두 번째 행부터, 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다. 
→ pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]

출력할 때는 n번째 행에 있는 k번째 수인 pascal[n-1][k-1]을 출력하면 된다.

n, k = map(int, input().split())

pascal = [[1 for _ in range(i)] for i in range(1, 31)]
for i in range(2, n):
    for j in range(1, i):
        pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]

print(pascal[n-1][k-1])

🪄 Four Squares

모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명했다.
자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 문제

import math

n = int(input())
dp = [0, 1]

for i in range(2, n+1):
    minValue = 1e9
    for j in range(1, int(math.sqrt(i))+1):
        minValue = min(minValue, dp[i-j**2])
    dp.append(minValue+1)

print(dp[n])

n보다 작거나 같은 제곱수를 찾고 n-제곱수를 인덱스로 가진 값에 1을 더해주면 된다.

🪄 피보나치 비스무리한 수열

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구하는 문제

n = int(input())
dp = [1] * 117
for i in range(4, n+1):
    dp[i] = dp[i-3] + dp[i-1]

print(dp[n])

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. 이 식을 그대로 사용해서 답을 구하면 된다.