9184번: 신나는 함수 실행

문제 풀이 아이디어

그냥 재귀함수만 구현하면 엄청나게 많은 함수를 중복으로 실행하므로 콜스택이 남아있지 않을 것입니다. 따라서 동적계획법을 활용해서 이미 구한 함수의 값은 3차원 배열의 cache에 저장해둡시다.

문제 자체에 모든 조건과 점화식이 있습니다. 함수를 구현하는 것 자체는 어렵지 않습니다.

코드

// cache 선언
var cache = Array(repeating: Array(repeating: Array(repeating: -1, count: 21), count: 21), count: 21)

func w(_ a: Int, _ b: Int, _ c: Int) -> Int {
    if a <= 0 || b <= 0 || c <= 0 {
        return 1
    } else if a > 20 || b > 20 || c > 20 {
        return w(20, 20, 20)
    } else if a < b && b < c && cache[a][b][c] < 0 {
        cache[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    } else if cache[a][b][c] < 0 {
        cache[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    }
    
    return cache[a][b][c]
}

while true {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let (a, b, c) = (input[0], input[1], input[2])
    if a == -1 && b == -1 && c == -1 { break }
    print("w(\(a), \(b), \(c)) = \(w(a, b, c))")
}