Algorithm PS/BOJ
[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬
migrationArc
2021. 7. 19. 23:54
[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬
https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
풀이
주어진 숫자를 1, 2, 3 으로 표현하는 경우의 수는 점화식으로 표현 가능하다.
dp(1) = 1
dp(2) = 2
dp(3) = 4
dp(4) = dp(1) + dp(2) + dp(3)
dp(N) = dp(N-3) + dp(N-2) + dp(N-1)
N = int(input())
nums = [0, 1, 2, 4]
for _ in range(4, 12):
nums.append(sum(nums[-3:]))
for _ in range(N):
print(nums[int(input())])