9461번: 파도반 수열

문제풀이 아이디어

1. 정의
    f(i) : i번째 정삼각형의 변의 길이
2. 구하는 답
    f(n)
3. 초기값
    f(1) = 1
    f(2) = 1
    f(3) = 1
    f(4) = 2
    f(5) = 2
4. 점화식
    f(i) = f(i - 1) + f(i - 5)

코드

// 파도반 수열

// f(n) = f(n - 1) + f(n - 5)

var cache = Array(repeating: -1, count: 101)

func f(_ n: Int) -> Int {
    if n > 0 && n < 4 {
        cache[n] = 1
    }
    
    if n >= 4 && n <= 5 {
        cache[n] = 2
    }
    
    if cache[n] < 0 {
        cache[n] = f(n - 1) + f(n - 5)
    }
    
    return cache[n]
}

let T = Int(readLine()!)!

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