[백준/파이썬] 9095번

📍백준 9095번 문제

코드

import sys
input = sys.stdin.readline


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


test_case = int(input())

for _ in range(test_case):
    num = int(input())
    print(plus(num))

풀이

• 1 = 1 (1개)
• 2 = 1+1 , 2 (2개)
• 3 = 1+1+1, 2+1, 1+2, 3 (4개)
• 4 = 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2, 3+1, 1+3 (7개)
• 5 = 1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+2+1, 2+1+2, 1+2+2, 3+1+1, 1+3+1, 1+1+3, 3+2, 2+3 (13개)

5를 보면 13개 = 7+4+2, 즉 4일 때의 값 + 3일 때의 값+ 2일 때의 값을 더하면 된다.
n = (n-1)+(n-2)+(n-3)이므로 재귀를 통해 풀면된다.