[백준_15991] 1,2,3 더하기 6 python

규칙 찾는데 진짜 시간 오래걸린다 이런문제는

개인적으로 이런류는 그냥 무지성 냅다 n = 10 까지 지르고

그리고 어거지로 규칙 찾는게 답인 듯 하다.

# dp 설계
dp = [
    0 for _ in range(100001)
]

# dp 초기설정
dp[1] = 1
dp[2] = 2
dp[3] = 2
dp[4] = 3
dp[5] = 3
dp[6] = 6

# dp 채워넣기
for i in range(7, 100001):
    dp[i] = (dp[i-2] + dp[i-4] + dp[i-6]) % 1000000009

# t 입력
t = int(input())
for _ in range(t):
    # n 입력
    n = int(input())
    # 출력
    print(dp[n] % 1000000009)