[알고리즘/DP] 9461번 : 파도반 수열 - python

링크 : https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

---

• 문제
• 소요시간 : 7분 52초

---

• 설계하기(접근방법) 

1. 입력받기

테스트 케이스 개수와

n을 입력받는다

 

2. 구현하기

n 이 1~ 100까지 들어오니

dp를 100까지 선언해준다

 

그림을 주어서 편하게 문제를 풀 수 있었다

 

그림을 보면

다음 정삼각형의 길이는

 

직전의 정삼각형의 길이 : dp[n-1]

5번쨰 전의 정삼각형의 길이 : dp[n-5]의

길이를 합한 것을 볼 수 있다

 

3. 출력하기

dp[n]을 출력한다

 

 

---

• 코드(출력)

dp = [0 for _ in range(101)]
dp[1], dp[2], dp[3], dp[4], dp[5] = 1, 1, 1, 2, 2
dp[6], dp[7], dp[8], dp[9], dp[10] = 3, 4, 5, 7, 9

for i in range(11, 101):
    dp[i] = dp[i-1] + dp[i-5]

for i in range(int(input())):
    n = int(input())
    print(dp[n])

---

• 얻어갈 부분