BOJ_9461 : 파도반 수열

👉 문제링크

9461번: 파도반 수열

---

---

🔸 문제 분석 🔸

• 규칙처럼 회오리 모양으로 삼각형이 늘어갈때 가장 큰 변의 길이를 출력하는 문제이다.
• dp[0] ~ dp[9] 까지의 10개 값은 문제에서 주어졌다.
• 인덱스 3(입력 값 4)부터 점화식이 적용된다.
  • P(N) = P(N-2) + P(N-3)

🔸 코드 🔸

dp = [1,1,1,2,2,3,4,5,7,9]

for _ in range(int(input())):
    n = int(input())

    if n <= len(dp):
        print(dp[n-1])
    else:
        for _ in range(n-len(dp)):
            dp.append(dp[-2]+dp[-3])
        print(dp[n-1])

🔸 코드 해석 🔸

• dp 리스트에 문제에서 주어진 10개의 값을 저장하고 시작했다.
• 주어진 값(n)이 dp 리스트의 크기보다 크다면(없는 인덱스라면), 그 차이만큼 계산해서 dp 리스트를 늘려준다.
• 해당 dp 리스트 인덱스 값을 출력한다.

---

🔸 end 🔸

• 답안을 찾아보지 않고 풀이한거라 수학적 원리를 설명하기가 좀 어려운 것 같다.
• 그냥 규칙찾기같은 문제였는데 dp 문제들을 간단히 풀을땐 이런 방법도 자주 사용되는 것 같다.
• dp 리스트 출력의 인덱스를 -1 해줘야하는데, 그걸 하나만 바꿔줘서 1회 틀렸다.