[BaekJoon] 9095번 1, 2, 3 더하기 (Silver 3) - Python

문제

 

정수 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의 합으로 나타내는 방법의수를 구하는 프로그램을 작성하시오.

---

입출력 예시

 

입력: 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력: 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

예제 입력1)

3

4

7

10

 

예제 출력1)

7

44

274

---

코드

 

# dp함수 작성
def dp(n: int) -> int:
    if n == 1: return 1
    elif n == 2: return 2
    elif n == 3: return 4
    else: return dp(n - 1) + dp(n - 2) + dp(n - 3) # 점화식
    # 1일 때 1가지
    # 2일 때 2가지
    # 3일 때 4가지
    # 4일 때 7가지
    # 5일 때 13가지
    # 6일 때 24가지
    # .
    # .
    # .
    # n일 때 (n-1의 경우의수 + n-2의 경우의수 + n-3의 경우의 수) 가지 -> 점화식

# n 입력
N = int(input())

# 숫자를 저장할 리스트 생성
nums = list()

# n개의 숫자 입력하여 리스트에 저장
for _ in range(N):
    a = int(input())
    nums.append(a)

# 리스트의 숫자를 하나씩 가져와서 dp함수에 대입, 출력
for a in nums:
    print(dp(a))

---

실행 화면

 

실행 화면

---

채점 결과

채점 결과