9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
1, 1, 1, 2, 2가 되기까지 규칙을 모르겠다가 그 후로부터 첫 요소와 끝 요소가 합해져서 3, 두 번째 요소와 끝 요소가 합해져서 4 ... 등등으로 쭉 늘어나는 규칙을 확인했다.
dp[n] = dp[n-1] + dp[n-5] (점화식)
t = int(input())
for _ in range(t):
num = int(input())
arr = [1, 1, 1, 2, 2]
if num > 4:
for i in range(5, num):
arr.append(arr[i-1]+arr[i-5])
print(arr[num-1])또 다른 규칙은, 1, 1, 1 이후로 i와 i+1의 합이 i+3번째인 것이다.
반응형