99클럽 코테 스터디 4기 29일차 TIL - 백준: 파도반 수열(9461) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	9461	파도반 수열	DP	실버3	Swift, Python

🚀 나의 접근 방법

P(1)부터 P(10)까지 첫 10개 숫자 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 에서 점화식을 찾으면 매우 쉽게 해결할 수 있다.

유심히 봐보면 다음과 같은 점화식을 만들 수 있다. P(N) = P(N-2) + P(N-2)

위 점화식으로 dp 테이블을 채우고 테스트 케이스를 출력하면 된다.

✍️ 나의 코드

Swift

let N = Int(readLine()!)!
var dp = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9] + Array(repeating: 0, count: 90)

for i in stride(from: 10, to: 100, by: 1) {
    dp[i] = dp[i-2] + dp[i-3]
}

for _ in 0..<N {
    print(dp[Int(readLine()!)!-1])
}

Python

N = int(input())
dp = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9] + [0] * 90

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

for _ in range(N):
    print(dp[int(input())-1])

🤔 회고

오늘은 해결하기 쉬운 문제가 나왔다.