[백준] 9095번 파이썬 (1, 2, 3 더하기)

1. 문제와 예제

(문제 링크: https://www.acmicpc.net/problem/9095)

9095번: 1, 2, 3 더하기

문제

예제

---

2. 전체 코드

import sys
input = sys.stdin.readline

# 입력 받기
T = int(input().rstrip()) # 테스트 케이스 수

for _ in range(T):
    n = int(input().rstrip()) # 정수
    dp = [0] * 11 # DP 테이블
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    for i in range(4, 11):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

    # 결과 출력하기
    print(dp[n])

---

3. 코드 해설

n = 1 ~ 6까지 다 써놓고 보니

n = 1 => 결과 1

n = 2 => 결과 2

n = 3 => 결과 4

n = 4 => 결과 7

n = 5 => 결과 13

n = 6 => 결과 24

n = 7 => 결과 44

i>=4에 대해 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]이 성립한다는 규칙이 보였다.

왜 이 규칙이 성립하는 것인지 생각해보니

dp(n)은

1. (n-1)에 대해 앞에 더하기 1을 붙인 식

2. (n-2)에 대해 앞에 더하기 2를 붙인 식

3. (n-3)에 대해 앞에 더하기 3을 붙인 식

세 식들을 모두 갖고 있기 때문에 개수를 더하면 된다.

따라서 점화식을 쓰듯이 dp[1], dp[2], dp[3]의 값은 직접 입력하고 dp[4]부터 dp[10](n 최댓값 10)까지는 식을 사용해서 구해내면 된다.