[백준] 파도반 수열 (9461)

문제 설명

백준 9461번 문제 링크

입력 및 출력

» 입력

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

» 출력

각 테스트 케이스마다 P(N)을 출력한다.

예제 입출력(테스트케이스)

입력	출력
2 6 12	3 16

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ9461_SWIFT
//
//  Created by choiyoujun on 2022/02/14.
//

let T = Int(readLine()!)!
var dp = [Int](repeating: -1, count: 101)

func wave(N: Int) -> Int {
    if dp[N] == -1 {
        dp[N] = wave(N: N - 2) + wave(N: N - 3)
    }
    
    return dp[N]
}

dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 2
dp[5] = 2
dp[6] = 3
dp[7] = 4
dp[8] = 5
dp[9] = 7
dp[10] = 9

for _ in 0..<T {
    let N = Int(readLine()!)!
    print(wave(N: N))
}