백준 - 고층 빌딩 (1328)

let MOD = 1000000007
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, L, R) = (input[0], input[1], input[2])
var dp = Array(repeating: Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1), count: N + 1)

dp[1][1][1] = 1

for i in stride(from: 2, through: N, by: 1) {
    for j in 1...L {
        for k in 1...R {
            dp[i][j][k] = (dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + dp[i - 1][j][k] * (i - 2)) % MOD
        }
    }
}

print(dp[N][L][R])

N-1개의 빌딩을 배치하는 모든 경우의 수를 알고 있다고 가정한 후 남은 1개의 빌딩을 어디에 배치해야 할지 생각한다.

이때 이 배치하는 빌딩을 가장 작은 빌딩이라고 생각하면 명확하게 세 가지 경우로 나눌 수 있다.

• 왼쪽에 배치하는 경우 → 왼쪽에서 보이는 빌딩 수 1 증가
• 오른쪽에 배치하는 경우 → 오른쪽에서 보이는 빌딩 수 1 증가
• 가운데 배치하는 경우 → 양쪽 빌딩 수 증가 X

이 아이디어를 가지고 점화식을 다음과 같이 도출할 수 있다.

• 왼쪽에 빌딩을 1개 추가하는 경우: dp[N - 1][L - 1][R]
• 오른쪽에 빌딩을 1개 추가하는 경우: dp[N - 1][L][R]
• 가운데 빌딩을 1개 추가하는 경우: dp[N - 1][L][R] * (N - 2)
  • 빌딩을 추가할 수 있는 자리가 N - 2개이기 때문에 N - 2를 곱한다.