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

9095번 : 1,2,3 더하기

이런 수학 적 문제는 진짜 진짜 머리가 아프고 힘들다..

combination 을 써서 구해야 하나 생각을 했는데 그러면 당연히 시간초과가 걸릴 것 같아 해보지는 않았다.

n 이 최대 11이라서 혹시 규칙이라도 있을까 싶어 1, 2, 3, 4, 5, 6, 7 까지 답을 계산 해 보았다.

1, 2, 4, 7, 13, 24, 44 이 나오게 되어 계차수열인가.. 계차수열 안에 계차수열인가.. 있을만한 규칙은 다 생각 해 보았다.

arr[n] = arr[n - 3] + arr[n - 2] + arr[n - 1] 의 규칙이 보인다.. 이 규칙으로 배열을 초기화 한 후 출력하면 된다.

다른 사람들은 어떻게 규칙을 발견했나 싶어 검색을 해봤는데 역시 내가 제일 멍청한 것 같다..

만약 4를 기준으로 본다면 4는 1+3 이므로 1+ 로 시작하는 식은 3의 답의 갯수와 같다.

또 2+2 이므로 2+ 로 시작하는 식은 2의 답의 갯수와 같다.

마지막으로 3+1 이므로 3+ 로 시작하는 식은 1의 답의 갯수와 같다.

따라서 위 와 같은 점화식이 만들어진다고한다.. 정말 대단하다..

---

import sys

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

for _ in range(t):
	num = sys.stdin.readline().rsplit()[0]
	print(arr[int(num) - 1])