백준 / 1, 2, 3 더하기 / 9095번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 1, 2, 3 더하기 / 9095번 (실버 3단계)

문제 사이트: https://www.acmicpc.net/problem/9095

 

문제 설명

---

나의 풀이

def solution(N):
    dp = [0] * (N + 1)

    # 초기값 설정, N의 크기에 따라 다르게 설정
    dp[0] = 1
    if N >= 1:
        dp[1] = 1
    if N >= 2:
        dp[2] = 2
    if N >= 3:
        dp[3] = 4

    # 점화식에 따라 dp 배열 채우기
    for i in range(4, N + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    
    return dp[N]

# 테스트 개수
T = int(input())

# 테스트 결과 값 담는 곳
result = []

for _ in range(T):
    n = int(input())
    result.append(solution(n))

# 결과 값 출력
for i in result:
    print(i)

이 풀이는 dp[i] = dp[i − 1] + dp[i − 2] + dp[i − 3] 이 점화식 기반해서 사용된다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/175

동적계획법(Dynamic Programming)