소스코드
T = int(input())
P = [0 for i in range(101)]
P[1] = 1
P[2] = 1
P[3] = 1
P[4] = 2
P[5] = 2
for i in range(T) :
n = int(input())
for j in range(6,n+1) :
P[j] = P[j-1] + P[j-5]
print(P[n])
주어진 그림을 보면,
3 = 2 + 1
4 = 3 + 1
5 = 4 + 1
7 = 5 + 2
9 = 7 + 2
임을 알 수 있다.
즉, P[6]번 째부터 P[n] = P[n-1] + P[n-5] 가 성립함을 알 수 있다.
'알고리즘 > 동적프로그래밍(DP)' 카테고리의 다른 글
[Python] 백준 2011번: 암호코드 풀이 (0) | 2021.02.04 |
---|---|
[Python] 백준 2225번: 합분해 풀이 (0) | 2021.02.03 |
[Python] 백준 2133번: 타일 채우기 풀이 (1) | 2021.01.26 |
[Python] 백준 1699번: 제곱수의 합 풀이 (0) | 2021.01.26 |
[Python] 백준 2579번: 계단 오르기 풀이 (0) | 2021.01.25 |
댓글