[백준/Python] 9095번 : 1, 2, 3 더하기

문제

https://www.acmicpc.net/problem/9095

n이 입력되면 1, 2, 3만으로 덧셈을 구할 수 있는 방법의 수를 출력한다.

 

나의 풀이

재귀를 사용한 방법이다.

1 2 3 중 하나를 선택하는 걸 반복하면서 sum에 더해주다가 sum이 n 되면 cnt를 올려준다.

import sys

t = int(sys.stdin.readline())

for i in range(t):
    N = int(sys.stdin.readline())
    cnt = 0
    def recur(n, sum_):
        global cnt
        if n<sum_:
            return
        if n==sum_:
            cnt += 1
            return
        recur(n, sum_ + 1)
        recur(n, sum_ + 2)
        recur(n, sum_ + 3)


    recur(N, 0)

    print(cnt)

 

다른 풀이

점화식과 초기값을 사용해 푼 방법이다. 

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

f(1) = 1 (1)

f(2) = 2 (1+1, 2)

f(3) = 4 (1+1+1, 1+2, 2+1, 3)

test_case = int(input())
d = [0, 1, 2, 4]
for i in range(4, 11):
  d.append(d[i-3] + d[i-2] + d[i-1])

for i in range(test_case):
  input_int = int(input())
  print(d[input_int])