[백준] 9461 파도반 수열 with Python

📌 BOJ 9461 파도반 수열

💡 조건

1. 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다.
   (1 ≤ N ≤ 100)

2. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이.

3. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

4. 각 테스트 케이스마다 정수 N을 입력받아 P(N)을 출력.

5. Dynamic Programming 알고리즘 유형의 문제

🖥 소스 코드

from sys import stdin

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

for i in range(3, 101):
    dp[i] = dp[i - 3] + dp[i - 2]

for _ in range(int(stdin.readline())):
    print(dp[int(stdin.readline()) - 1])

🔖 예제 및 실행결과

예제

2
6
12

실행결과

3
16

⌨️ 문제 풀이

1. 문제에서 이미 점화식을 짜라고 P(1)부터 P(10)까지 제공해주었다.
   규칙을 찾아 점화식을 세워보자면, dp[i] = dp[i - 3] + dp[i - 2] 이 될 것이다.

2. 여기서 N의 범위를 살펴보면 1부터 100까지 이다.

3. 배열의 크기를 101개로 둔 뒤, 문제에서 제공해준 값을 다 넣어도 좋고, 앞의 세개만 넣어 점화식을 통해
   101개의 배열을 채우는 것도 좋다.

4. 배열을 채우는데에는 큰 시간이 걸리지 않으니, 미리 모두 구해놓고 테스트케이스마다 입력을 받아 처리했다.
   • 여기서, dp 리스트의 N-1번째를 출력하지 않으면 엉뚱한 답이 나오거나, index에러를 뱉고 죽어버릴 수 있으니 조심하자.

💾 느낀점

1. 너무나도 상냥하고 친절한 DP문제였다.