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

---

문제

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

---

문제 이해(점화식 찾기)

먼저 이 문제는 규칙을 찾아야 한다.

n	ans
1	1
2	1
3	1
4	2
5	2
6	3
7	4
8	5
9	7
10	9
11	12
12	16​

 

n이 1부터 10까지의 답은 문제에 주어져 있어서 규칙을 쓰고 살펴보기 시작했다.

n이 10일 경우 답이 9인데 9=4+5라는 것이 딱 보인 후 다른 값들을 살펴보니 정규식을 찾을 수 있었다.

 

dp[n] = dp[n-2] + dp[n-3]

---

문제 풀이(정답)

T = int(input())

for _ in range(T):

    n = int(input())

    dp = [1] * (n+1)

    for i in range(4, n+1):

        dp[i] = dp[i-2] + dp[i-3]

    print(dp[-1])

 

다이나믹 프로그래밍을 이용해 문제를 풀어주었다.

다이나믹 프로그래밍은 점화식만 구한다면 이제 막힘없이 풀 수 있을 것 같다! 꽤 익숙해진 느낌이다~