[백준] 9095_1, 2, 3 더하기 (Python)

[문제번호]_[문제이름] (Python)

0. 출처

• 유형 : DP (silver 3)
• 링크 : 9095번: 1, 2, 3 더하기

1. 기록

• 22/06/30 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> DP 문제 (tabulation 으로 푼다.)
>> 1. 테이블 정의
dp = [0 for _ in range(11)]

>> 2. 초깃값 삽입
dp[1]+3
dp[2]+2
dp[3]+1


>> 3. 테이블 채우기
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
4
7
10


- 예제 출력 1 -
7
44
274

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def dp_func(n):
    # fixme - 1. 테이블 정의
    dp = [0 for _ in range(11)]     # n은 11보다 작다는 조건이 있음, 테이블 크기를 11만큼 해주자

    # fixme - 2. 초깃값 삽입
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    dp[4] = 7

    # fixme - 3. 테이블 채우기
    for i in range(5, n+1):
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

    print(dp[n])

for _ in range(t):
    n = int(input())
    dp_func(n)

(4) 정리

DP 문제 풀면 짜릿하다.

(5) 참고