백준 11001 김치

https://www.acmicpc.net/problem/11001

날짜와 시간제한이 주어질 때 각 날짜별 온도 Ti와 가치 Vi가 주어진다. 이 때 i일에 김치를 넣어서 j일에 김치를 꺼낸다면 (j-i)*Tj + Vi 로 정의되는 김치의 맛의 최댓값을 구하는 문제이다.

c[i][j] = (j-i)*Tj + Vi 로 c 함수를 정의하자. 즉 i일에 넣어서 j일에 꺼낼 때의 김치의 맛이 정의되어있다. 그런데 이 c함수는 Monge Array라는 것을 Monge Array 조건에 대입해보면 확인할 수 있다. 그렇다면 앞에서의 분할 정복 트릭을 생각해보자.

dp[i][j] = min(dp[i-1][k] + c[k][j]) where k < j && c[i][j] is Monge Array

그런데 여기서는 i라는 것이 없다. 따라서 이전 dp 값은 모두 없고 1차원 dp를 구한다고 생각해보자. 그렇다면 식은 다음처럼 변한다.

dp[j] = min(c[k][j]) where k < j && c is Monge Array

아하. 그렇다면 dp[j]를 j날에 김치를 꺼낼 때 가장 맛있는 김치값이라 정의하고 그것을 만족하는 k를 opt_j라고 할 수 있을 것이다. 그렇다면 j일보다 나중에 김치를 꺼낸다고 한다면 그때의 최솟값을 얻게해주는 opt 값은 k보다 크거나 같다는 것을 알 수 있다.

이해가 잘 안가는 사람은 위의 그림을 보자. 만약 정중앙 날짜의 해답이 노란색 화살표로 표시되어있을 때 해당 날짜보다 왼쪽 날짜들의 최적해는 노란색 최적해보다 작거나 같고 정중앙 날짜보다 오른쪽 날짜들의 최적해는 노란색 최적해보다 크거나 같다. 따라서 분할 정복으로 정중앙 값을 구하고 왼쪽 영역과 오른쪽 영역에 대해 각각 분할 정복을 반복적으로 실시해주면 된다.

• dnc 코드 일부

var k = max(l, m-d)
for i in k...min(r, m) {
    if c(i: k, j: m) < c(i: i, j: m) {
        k = i
    }
}

코드를 보면 알겠지만 dnc 중간 부분에서 위의 코드가 나온다. 원래는 함수의 입력으로 들어온 l부터 r로 범위를 사용해야하나 max와 min값으로 범위를 제한해주는데 최대 d일까지 떨어져있을 수 있다는 조건과 집어넣은 날이 꺼내는 날보다 나중에 있을 수는 없기 때문에 범위를 제한해주었다.

• 전체 코드

let nd = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nd[0], d = nd[1]
let t = readLine()!.split(separator: " ").map{Int(String($0))!}
let v = readLine()!.split(separator: " ").map{Int(String($0))!}
var result:Int64 = 0
dnc(s: 0, e: n-1, l: 0, r: n-1)
print(result)

func c(i: Int, j: Int) -> Int64 {
    return Int64(j-i)*Int64(t[j])+Int64(v[i])
}

func dnc(s: Int, e: Int, l: Int, r: Int) {
    if s > e {
        return
    }
    let m = (s+e)/2
    var k = max(l, m-d)
    for i in k...min(r, m) {
        if c(i: k, j: m) < c(i: i, j: m) {
            k = i
        }
    }
    result = max(result, c(i: k, j: m))
    dnc(s: s, e: m-1, l: l, r: k)
    dnc(s: m+1, e: e, l: k, r: r)
}