[Python Algorithm] 파도반 수열 BOJ #9461

문제

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

9461번: 파도반 수열

 

내 문제 풀이

t = int(input())
memory = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
n = []
for _ in range(0, t): n.append(int(input()))

if max(n) > 10:
    num = 10
    while num < max(n):
        memory.append(memory[num-1] + memory[num-5])
        num += 1

for i in n: print(memory[i-1])

👉 DP 문제로, 점화식을 구하고 메모이제이션 활용하는게 포인트!

 

[점화식]

• p(1) = 1
• p(2) = 1
• p(3) = 1
• p(4) = 2
• p(5) = 2
• p(6) = 3 = p(5) + p(1)
• p(7) = 4 = p(6) + p(2)

=> p(n) = p(n-1) + p(n-5) (n > 5)

(이 점화식은 사실 이렇게 써보는 것보다, 문제에서 주어진 그림에서

해당 숫자가 쓰여진 삼각형 한 변을 이루는게 몇 번째 삼각형들의 변으로 이루어졌는지를 보면 바로 알 수 있다.)

 

[풀이 설명]

• 이미 구해진 10까지의 변의 길이는 미리 memory 리스트에 넣어두고,
  문제에서 주어진 입력을 모두 받은 후 그 입력들 중 가장 큰 수가 10보다 클 경우에만
  memory 리스트에 연산 값을 추가해주는 반복 연산을 시행해주었다.
• 반복 연산은 위에서 구한 점화식을 이용하여, while문으로 구현했다.

 

💡 피드백

• 그림을 보고 바로 점화식을 떠올릴 수 있는 문제였고, 금방 풀었다.