128. 9461 (파도반 수열)

T = int(input())
result = []

arr = [0] * 1001
for _ in range(T):
  N = int(input())
  arr[1], arr[2], arr[3] = 1, 1, 1

  for i in range(4,N+1):
    arr[i] = arr[i-2] + arr[i-3]

  result.append(arr[N])
  
print("\n".join(map(str,result)))

문제요약

작은삼각형이 나선형으로 커지는데 입력값에 따른 삼각형의 개수를 구하시오.

설명

매우 쉬운문제이다.

P(N)에 따른 개수는 다음과 같으며, 3까지는 1로 그 이후에는 P(N) - 2 + P(N) - 3 의 피보나치형태를 띄운다.

 

따라서 

    arr[i] = arr[i-2] + arr[i-3]

이 로직을 통해 쉽게 구할 수 있다.

 

N에따른 결과를 바로 출력하기 위해 arr[0]은 비워 두었으며, 메모리 공간을 아끼고 싶다면

-1씩 붙여주면 된다.