문제 : www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
풀이
dp에 P(n)의 값을 저장한다.
n이 5 이상이 되면 해당 값은 P(n-5)+P(n-1)의 값을 가진다.
t = int(input())
dp = [0, 1, 1, 1, 2]
for _ in range(t):
n = int(input())
if n > len(dp)-1:
for i in range(len(dp),n+1):
dp.append(dp[i-5]+dp[i-1])
print(dp[n])'알고리즘 풀이 > 백준' 카테고리의 다른 글
| 백준 11712번 : 2×n 타일링 2 (Python) (0) | 2021.02.07 |
|---|---|
| 백준 1010번 : 다리 놓기 (Python) (0) | 2021.02.06 |
| 백준 1932번 : 정수 삼각형 (Python) (0) | 2021.02.04 |
| 백준 2156번 : 포도주 시식 (Python) (0) | 2021.02.04 |
| 백준 11053 : 가장 긴 증가하는 부분 수열 (Python) (0) | 2021.02.04 |