9095번: 1, 2, 3 더하기

문제 풀이 아이디어

점화식을 찾으면 쉽게 풀 수 있는 DP 문제입니다. 점화식은 아래와 같습니다.

1. f(i) = i를 1, 2, 3의 합으로 나타내는 방법의 수입니다.
2. f(1) = 1
    f(2) = 2
    f(3) = 4
3. f(i) = f(i - 3) + f(i - 2) + f(i - 1)

코드

// 1, 2, 3 더하기

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

func f(_ n: Int) -> Int {
    // 1, 2, 3일 때 초기값
    if n == 1 || n == 2 {
        cache[n] = n
    }
    if n == 3 {
        cache[n] = 4
    }
    
    // 점화식
    if cache[n] < 0 {
        cache[n] = f(n - 3) + f(n - 2) + f(n - 1)
    }
    
    return cache[n]
}

// 입력 받기
let T = Int(readLine()!)!

for _ in 0..<T {
    let n = Int(readLine()!)!
    print(f(n))
    //👉 여기서 f를 계속 실행해도 처음부터 다시 구하는 것이 아니라 cache에 저장된 것을 사용하기에 문제 없음
}