Boj9095

9095 1, 2, 3 더하기

---

layout: post title: “[Python] 9095 1, 2, 3 더하기” date: 2021-11-27 categories: ps tags: “ps” —

문제 유형에 놀랐다…

음…

난 무작정전략인줄…

1 -> 1 1가지

2 -> 1+1

​ 2 2가지

3 -> 1+1+1

​ 1+2

​ 2+1

​ 3 4 가지

4 -> 1+1+1+1

​ 1+1+2

​ 1+2+1

​ 1+3

​ 2+1+1

​ 2+2

​ 3+1 7가지

아 이렇게 쓰고 보니까 DP라는거 알 것 같다.

가지를 하나 놓고 쪼개면 그 뒷부분은 전 단계의 수가 된다.

T(n) = T(n-1) + T (n-2) + T(n-3)

이걸 거다 초항은 1, 2, 3이고

# 9095 1,2,3더하기

def A(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    return A(n-1) + A(n-2) + A(n-3)


T = int(input())
for i in range(T):
    n = int(input())
    result = A(n)
    print(result)

정답쓰

교훈

• 처음 몇가지 경우는 세 보자.
• 1+1+2와 1+2+1이 별개다…