728x90
😉 아이디어
1. _!n이 7미만일 경우!_까지 각 특수한 조합 개수 확인 👉 _![1, 2, 5, 2, 2, 4]!_반복됨
2. 3의 배수로 반복되고 있으므로_!f(n + 3) - f(n)!_를 통해 _!f(n)!_의 점화식 계산
😉 풀이
def solution(n):
dp = [0] * (n + 10)
dp[1] = 1
dp[2] = 3
dp[3] = 10
MOD = 1_000_000_007
# n이 6 이하인 경우 저장
for i in range(4, n + 1):
if i == 4:
dp[i] = dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 5 + 2
elif i == 5:
dp[i] = dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 5 + dp[i - 4] * 2 + 2
elif i == 6:
dp[i] = dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 5 + dp[i - 4] * 2 + dp[i - 5] * 2 + 4
if n < 7:
return dp[n]
# n이 7을 넘어가면 점화식으로 계산
for i in range(7, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 6 + dp[i - 4] - dp[i - 6]) % MOD
return dp[n]✔ 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/181186
