문제 링크 (opens new window)

풀이

1. 같은 것이 있는 순열 공식에 따라 풀이를 진행
2. 팩토리얼 계산만 재귀가 아닌 DP로 풀이
3. 최악의 경우 11! 계산 결과가 39916800이므로 오버플로우 발생하지 않음

import Foundation

let T = Int(readLine()!)!
// a+b+c! / a!b!c!
// 1 * x + 2 * y + 3 * z == n

func factorial(_ n: Int) -> Int {
    var dp: [Int] = .init(repeating: 0, count: n + 1)
    dp[0] = 1
    if n == 0 {
        return 1
    }
    for i in 1...n {
        dp[i] = dp[i-1] * i
    }
    return dp[n]
}

for _ in 0..<T {
    let n = Int(readLine()!)!
    var tuple: [(Int, Int, Int)] = []
    for i in 0...n {
        for j in 0...n {
            for k in 0...n {
                if i + 2 * j + 3 * k == n {
                    tuple.append((i,j,k))
                }
            }
        }
    }

    var sum = 0
    for tup in tuple {
        let (a,b,c) = tup
        sum += (factorial(a+b+c) / (factorial(a) * factorial(b) * factorial(c)))
    }
    print(sum)
}