Baekjoon15988 - 1,2,3 더하기 3(Python)

백준 사이트 15988 - 1,2,3 더하기 3 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

https://www.acmicpc.net/problem/15988

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

코딩테스트 준비-기초 : 브루트포스 - 다이나믹프로그래밍 문제입니다.

---

☑️ 4. 생각한 것들

• 중복여부를 검사하지 않으므로 점화식이 간단합니다.
• 직전 수에서 1을 더하는 경우
• 전전 수에서 2를 더하는 경우
• 전전전 수에서 3을 더하는 경우

즉, DP[n] = DP[n-1] + DP[n-2] + DP[n-3] 이라는 점화식이 나옵니다.

---

5. code

from sys import stdin
from collections import deque

input_list = []

dp = deque([0, 1, 2, 4])
max_num = 0
mod = 1000000009


def init():
    def data_input():
        t = int(stdin.readline())

        for i in range(t):
            input_list.append(int(stdin.readline()))

    data_input()
    global max_num
    max_num = max(input_list)


def result():
    for i in range(4, max_num + 1):
        dp.append((dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod)

    for data in input_list:
        print(dp[data])


def solution():
    init()
    result()


solution()

---

6. 후기

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.