Wednesday, August 26, 2015

Coder's High 2013 J번 Bookthief

평범한 0-1냅색이라고 가정하면 다음과 같은 DP식을 세울수있다.

D[N,V] := N종류의 아이템에 대해 고려해서, V칸을 채웠을때의 최대 값어치
D[N,V] = max{D[N−1,V],D[N−1,V−(volume of item)]+(value of item)}

vi=(volume of item), ci=(value of item)이라고 하고, 아이템의 갯수를 ki라 하자. 위의 식에서 0-1을 0-k로 확장시킨다는 느낌으로 식을 바꿔 써보면,

D[N,V] = max{D[N−1,V],D[N−1,V−vi]+ci,D[N−1,V−vi×2]+ci×2, ... ,D[N−1,V−vi×ki]+ci×ki}

묶어서 쓰면 다음처럼 쓸수있다.

D[N,V] = max{D[N−1,x]+(V−x)/vi×ci} (단,x≡V mod vi이고,V−vi×ki≤x≤V이다.)

x에 대한 식만 남기고 V에 대한 부분은 밖으로 뺄 수있다.

D[N,V] = max{D[N−1,x]−x/vi×ci}+V/vi×ci

f(x) = D[N−1,x]−x/vi×ci 라고 하자.

그렇다면 D[N,V]를 다음과 같이 구할수 있다.

1. f(V)값을 PQ에 넣는다.
2. PQ의 top인 x값이 V와 vi×ki를 넘게 차이나면 top을 제거한다
3. PQ의 top인 f(x)값에 대해 D[N,V]=f(x)+V/vi×ci이다.

최대 PQ의 크기는 O(V)이므로, 시간 복잡도는 O(NVlgV)이다. 이렇게 작성해도 AC를 받기엔 충분한 속도지만, 조금 더 속도 향상을 할 수 있다. PQ안에 있는 2개의 t1 < t2에 대해 생각해보자. 만약 f(t1) < f(t2)라면 t1은 PQ의 top이 영원히 될수 없다. 그러므로 이러한 t1은 전부 배제되었다고 가정하면,

1. PQ안 원소들의 x값들을 순서대로 x1<x2<x3..라 하면
2. f(x1)≥f(x2)≥f(x3)≥...을 만족한다.

또한 위의 조건을 만족하도록 PQ를 관리하여야 한다. 이러한 구조는 선형 deque로도 관리할수있으며, 매 원소는 최대 한 번 삽입과 삭제가 발생하게 되므로 이때의 시간 복잡도는 amortized O(NV)이다.

No comments:

Post a Comment