[backjoon] 9095 1, 2, 3 더하기

문제 9095번: 1, 2, 3더하기

Dynamic Programming

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1
  정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

예제 입력

3
4
7
10

예제 출력

7
44
274

---

문제풀이

이 문제는 점화식을 이용해서 푸는 문제이다.

• 1일 때 -> 1
• 2일 때 -> 2
• 3일 때 -> 4
• 4일 때 -> 7
• 5일 때 -> 13
  위와 같은 규칙을 나타내므로,
  f(n) = f(n-1) + f(n-2) + f(n-3) (n>3 인 경우) 의 식이 나오게 된다!

---

전체코드

import sys
input = sys.stdin.readline

T = int(input())

def sum(N):
    if N == 1:
        return 1
    elif N == 2:
        return 2
    elif N == 3:
        return 4
    else:
        return sum(N-1) + sum(N-2) + sum(N-3)

for i in range(T):
    num = int(input())
    print(sum(num))

출처 백준 알고리즘 파이썬(Python) 9095번 1, 2, 3 더하기