[백준] 9095번 1, 2, 3 더하기 파이썬

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

---

✔️문제

분류

다이나믹 프로그래밍(dp)

문제 설명

정수 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의 합으로 나타내는 방법의 수를 출력한다.

---

✔️풀이

다이나믹 프로그래밍은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

n이 1, 2, 3일 때 n을 나타내는 방법의 수는 다음과 같다
f(1) = 1, f(2) = 2, f(3) = 4

1. n이 4일 때,

4를 1,2,3으로 더하기 때문에, 1+3, 2+2, 3+1로 나눌 수 있다.

1+3	2+2	3+1
1+3	2+2	3+1
1+1+2	2+1+1
1+2+1
1+1+1+1

1+3은 3을 나타낼 수 있는 경우의 수와 같으므로 f(3)
2+2는 2을 나타낼 수 있는 경우의 수와 같으므로 f(2)
3+1은 1을 나타낼 수 있는 경우의 수와 같으므로 f(1)

f(4)=f(1)+f(2)+f(3)으로 나타낼 수 있다.

2. n이 5일 때,

5를 1,2,3으로 더하기 때문에, 1+4, 2+3, 3+2로 나눌 수 있다.

1+4	2+3	3+2
1+1+3	2+3	3+2
1+1+1+2	2+1+2	3+1+1
1+1+2+1	2+2+1
1+1+1+1+1	2+1+1+1
1+2+2
1+2+1+1
1+3+1

1+4은 4을 나타낼 수 있는 경우의 수와 같으므로 f(4)
2+3는 3을 나타낼 수 있는 경우의 수와 같으므로 f(3)
3+2은 2을 나타낼 수 있는 경우의 수와 같으므로 f(2)

f(5)=f(1)+f(2)+f(3)으로 나타낼 수 있다.

따라서 n을 나타내는 경우의 수는 다음과 같다.
f(n) = f(n-3) + f(n-2) + f(n-1) (n>3)

코드

import sys
input = sys.stdin.readline

def func(x):
  if x==1:
    return 1
  elif x==2:
    return 2
  elif x==3:
    return 4
  else:
    return func(x-1)+func(x-2)+func(x-3)

t = int(input())
for _ in range(t):
  n = int(input())
  print(func(n))