Python : 파도반 수열(재귀,DP)

문제

풀이

• 수열에서 규칙을 찾아 답을 구현하는 문제
• 그림을 잘 보면

  2 = 1+1
  3 = 1+2
  4 = 2+2
  ...

이런식으로 증가한다. 이 값은 문제에서 주어진 삼각형들의 값이다. 이를 통해
(n>3) An = An-3 + An-2 로 정의할 수 있다. 재귀로 풀 것이기 때문에 시간복잡도가 뭉개지는 것을 대비해서 DP배열을 만들고 한번 계산한 값은 바로 꺼내서 쓸 수 있도록 하자!

전체코드

dp = [0] * 101
dp[1], dp[2], dp[3] = 1, 1, 1


def sol(x):
    if dp[x] != 0:
        return dp[x]
    else:
        dp[x] = sol(x - 3) + sol(x - 2)

    return dp[x]


t = int(input())
for i in range(t):
    n = int(input())

    print(sol(n))