백준 13261 탈옥
23 Jun 2021https://www.acmicpc.net/problem/13261
죄수의 수와 간수의 수가 주어지고 각 죄수마다 탈옥력 Ci가 주어질 때 탈옥 위험도 Ri는 Ci와 i번칸을 감시하는 간수의 감시하는 죄수의 수를 곱한 값이라고 했을 때 모든 Ri를 더한 값이 최소가 되도록 하는 문제이다. dp[i][j]를 i명의 간수가 j번 죄수까지 감시를 할 때 탈옥 위험도의 최솟값이라 정의하자. 그러면 dp를 다음과 같이 쓸 수 있다.
dp[i][j] = min(dp[i-1][k] + c[k][j])
i-1명의 간수가 k까지 살펴본다고 할 때 i번째 간수는 k+1번 죄수부터 j번죄수까지를 살펴보면 된다. 따라서 c[k][j]는 (j-k)*(Sum[j]-Sum[k])라고 정의할 수 있다. 여기서 Sum이란 Ci들의 누적합을 의미한다. c함수는 Monge Array이기 때문에 DnC optimization을 적용할 수 있다.
여기서 유의할 것은 앞서 푼 김치 문제처럼 i가 1개인 1차원이 아니라 2차원이라는 점이다. 따라서 i값을 1부터 간수의 최대 수까지 증가시켜가면서 dnc를 해줘야 한다는 점이다. 최종적으로 원하는 값은 dp[간수의 수][죄수의 수]에 저장되어 있다.
개인적으로 분할 정복 트릭의 기본 형태 그대로 적용하는 문제였기 때문에 분할 정복 트릭을 이해하는데 꽤 괜찮은 문제라고 생각한다.
- 전체 코드
let lg = readLine()!.split(separator: " ").map{Int(String($0))!}
let l = lg[0], g = lg[1]
let c = readLine()!.split(separator: " ").map{Int64(String($0))!}
var dp:[[Int64]] = Array(repeating: Array(repeating: -1, count: l+1), count: g+1)
var opt = Array(repeating: Array(repeating: -1, count: l+1), count: g+1)
var sum:[Int64] = Array(repeating: 0, count: l+1)
for i in 1...l {
sum[i] = sum[i-1]+c[i-1]
dp[1][i] = sum[i]*Int64(i)
}
for t in 2..<g+1 {
dnc(s: 1, e: l, l: 1, r: l, t: t)
}
print(dp[g][l])
func dnc(s: Int, e: Int, l: Int, r: Int, t: Int) {
if s > e {
return
}
let m = (s+e)/2
for i in l...min(r, m) {
let dpVal = dp[t-1][i] + c(i+1, m)
if dp[t][m] == -1 || dp[t][m] > dpVal {
dp[t][m] = dpVal
opt[t][m] = i
}
}
dnc(s: s, e: m-1, l: l, r: opt[t][m], t: t)
dnc(s: m+1, e: e, l: opt[t][m], r: r, t: t)
}
func c(_ i: Int, _ j: Int) -> Int64 {
return (sum[j]-sum[i-1])*Int64(j-i+1)
}