14697번: 방 배정하기

문제 해결 아이디어

N명을 남는 침대 없이 방을 배정하기 위해서는 N - A 혹은 N - B 혹은 N - C 명을 침대 없이 방을 배정할 수 있어야 합니다.

1. 정의
    f(i) = i명의 학생을 주어진 조건에 맞게 방 배정을 할 수 있는지 여부
2. 구하는 답
    f(N)
3. 초기값
    f(A) = 1
    f(B) = 1
    f(C) = 1
4. 점화식
    f(n) = f(n - A) == 1 || f(n - B) == 1 || f(n - C) ? 1 : 0

코드

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

func f(_ n: Int) -> Int {
    if n <= 0 {
        return 0
    }
    
    if n == A || n == B || n == C {
        cache[n] = 1
    }
    
    if cache[n] < 0 {
        cache[n] = f(n - A) == 1 || f(n - B) == 1 || f(n - C) == 1 ? 1 : 0
    }
    
    return cache[n]
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (A, B, C, N) = (input[0], input[1], input[2], input[3])

print(f(N))