[Python] 백준 9461. 파도반 수열

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

9461번: 파도반 수열

DP문제.

그림 덕분에 쉽게 점화식이 유추 가능하다.

n번째 삼각형 = n-1번째 삼각형 + n-5번째 삼각형이므로

table[n] = table[n-1] + table[n-5] 형태의 함수를 구현하면 된다.

 

 

	import sys
	n = int(sys.stdin.readline())
	memo = {1:1,2:1,3:1,4:2,5:2}
	def find_result(number : int) -> int:
	if number in memo:
	return memo[number]
	memo[number] = find_result(number-1) + find_result(number-5)
	return memo[number]
	for _ in range(n):
	num = int(sys.stdin.readline())
	print(find_result(num))

view raw [백준] 파도반 수열.Py hosted with ❤ by GitHub