백준 9461 파도반 수열

✅ 백준 9461 파도반 수열

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

정답.

그림을 잘 보니 규칙이 보였다.

N번째 정삼각형의 변은 N-1번째의 정삼각형의 변과 N-5번째 정삼각형의 변의 합과 같았다.

P(N) = P(N-1) + P(N-5)

피보나치랑 닮았으니까, 5번째 변의 길이까지만 캐시에 넣어두고 동적 계획법으로 풀면 되겠다 싶었다.

import sys

cache = [-1]*101
cache[1], cache[2], cache[3], cache[4], cache[5] = 1, 1, 1, 2, 2

def p(k) :
    if cache[k] != -1 :
        return cache[k]

    result = p(k-1) + p(k-5)
    cache[k] = result
    return  result

test_case = int(sys.stdin.readline())

for i in range(test_case) :
    num = int(sys.stdin.readline())
    print(p(num))