[백준] 9461번 파도반 수열 (Python)

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

9461번: 파도반 수열

---

풀이 과정

① 문제 바라보기

 

관찰을 해보니 점화식 작성이 간단하게 됩니다. 알고보니 피보나치였음!

 

② 아이디어 열기

그럼 보톰업방식으로 해결이 아래와 같이 됩니다.

**보톰업방식: 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답이 도출되는 것

dp = [0 for _ in range(101)]
dp[1] = 1
dp[2] = 1
dp[3] = 1

for i in range(4,101):
    dp[i] = dp[i-3] + dp[i-2]
for _ in range(int(input())):
    print(dp[int(input())])

 

근데 알고보니 dp[i] = dp[i-5] + dp[i-1]도 된다는 사실을 알게됨. (왜냐하면 계속 시계방향으로 돌아가면서  삼각형이 생기니깐..

---

결론

점화식 문제는 예제를 정말 꼼꼼히 보자! 예제 안에 답이 있데이..