#5375 공책 구매

현재 시각 기준 15명에게밖에 풀려있지 않은 문제다.
매우 좋은 dp문제라는 생각이 들어서 풀이를 올린다.

 

1.배송비가 없다면 어떤 문제일까?

mcmf의 기본형태이다.

2.배송비가 있을때 naive한 dp를 떠올려보자.
그렇게 되면 시간복잡도가 test case1개당

$O(NMS)$정도에 풀수 있고, 이는 너무 크다.
(tc가 1개라면 적당히 최적화 할 여지가 존재한다.)

여기서 최적화를 잘하면 $O(NS)$정도에 줄일수도 있는데, 이렇게 해도, tc가 100개라 tle가 난다.(해보진 않음..ㅋㅋ!)

 

3.그리디한 전략 하나를 섞자.

i번째 쇼핑몰에서 구매하기로 결정했으면, 그 쇼핑몰에서 항상 모든 물건을 구매하거나, 
그 쇼핑몰이 마지막 쇼핑몰인 경우가 최적해이다.

 

proof: 모든 물건을 구매하지 않은 쇼핑몰 2개가 있다고 가정하자, pi가 큰쪽의 물건을 구매한것을 전부 철회하고, pi가 작은 쪽의 쇼핑몰에서 사면 된다. 따라서 한쇼핑몰은 항상 꽉찬다.

 

이렇게 되면 시간복잡도를 줄일수 있다.

여기서 중요한점은 pi를 기준으로 정렬을 하고 문제를 풀어야 한다는 점인데, 이해했다면 쉽게 추론할 수 있다.