9461 파도반수열

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

T = int(input())
N_array = []
for _ in range(T):
    N_array.append(int(input()))


def dp(N):
    # dp table 초기 설정
    dp_table = [0]*101
    dp_table[1] = 1
    dp_table[2] = 1
    dp_table[3] = 1
    dp_table[4] = 2
    dp_table[5] = 2

    for i in range(6,N+1):
        dp_table[i] = dp_table[i-5]+dp_table[i-1]
    return dp_table[N]

for j in range(T):

    print(dp(N_array[j]))

3. 문제 풀이

이런 그림으로 주어진 문제는 손으로 그림을 그려가면서 규칙을 찾아내야 한다. 시계방향으로 1,2,3,… 숫자를 세가면서 삼각형을 그리다보면, 6이상의 i번째 삼각형부턴 i-5번째,i-1번째의 삼각형의 빗변의 길이 합의 규칙을 갖는 것을 알 수 있다. 따라서 다음과 같은 점화식을 세워주면 된다.

\[dp\_table[i] = dp\_table[i-5]+dp\_table[i-1]\]