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

백준 9095 문제 바로가기

풀이 코드

# n = 1일 경우 1개, n = 2일 경우 2개, n = 3일 경우 4개, n = 4일 경우 7개, n = 5일 경우 13개
# n이 3보다 큰 경우부터는 f(n-1) + f(n-2) + f(n-3) = f(n)
t = int(input())  # 테스트 케이스 개수


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


for i in range(t):
    n = int(input())
    print(sol(n))

규칙을 찾아서 문제를 푸는 DP 문제다.
위 문제에서 찾은 규칙은 n이 1일 경우 결과값은 1개, n이 2일 경우 결과값은 2개, n이 3일 경우 결과값은 4개, n이 4일 경우 결과값은 7개, n이 5일 경우 결과값은 13개로 n이 3보다 클 때는 f(n) = f(n-1) + f(n-2) + f(n-3) 이라는 규칙을 찾았다!