현재 온라인 마켓에 있는 상품을 번 크림부터 번 크림이라고 하자. 어떤 두 상품 가 이고 를 만족한다면, 번 크림은 어떤 날짜에서도 번 크림보다 나은 선택이 될 수 없다. 따라서 실제로 사용될 가능성이 있는 크림만 남기면, 남은 크림들은 유통기한 오름차순으로 보았을 때 효과가 엄격히 내림차순이다.
이 남은 크림들의 집합을 라고 하자. 이고 라면, 최적 사용에서는 번 크림을 총 일 동안 사용한다. 여기서 이다. 따라서 실제로 사용한 크림들의 가격 합은
이다.
온라인 마켓의 모든 상품 가격 합을 라고 하면, 다다스가 구매한 크림들의 전체 가격 합은 이다. 그러므로 각 2번 질의의 답은 이다.
집합 는 유통기한을 기준으로 정렬된 std::set으로 관리한다. 새 상품 가 추가될 때, 에서 유통기한이 이상인 첫 원소를 찾는다. 이 원소의 효과가 보다 크면 새 상품은 지배되므로 에 넣지 않는다. 그렇지 않으면 유통기한이 이하이면서 효과가 보다 작은 원소들을 뒤에서부터 지운 뒤 새 상품을 삽입한다.
는 각 원소가 자신의 직전 원소와 만드는 구간 길이에 기여하는 값을 이용해 국소적으로 갱신할 수 있다. 원소 하나를 삭제하거나 삽입할 때 영향을 받는 항은 그 원소와 바로 다음 원소의 항뿐이다. 각 상품은 에 최대 한 번 삽입되고 최대 한 번 삭제되므로 전체 시간 복잡도는 이다.
Solution written by GPT5.5
