백준 5375 공책 구매 - C++

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

5375번: 공책 구매

 

<문제>

민혁이는 공책을 N개 사려고 한다. 민혁이는 온라인 쇼핑몰 M개에서 파는 공책의 가격을 모두 조사해놓았다.
i번째 쇼핑몰에서 파는 공책의 가격은 하나당 pi원이고, 총 si개가 준비되어 있다. 또, 배송비는 oi원이다. 민혁이는 si개를 넘게 주문할 수 없으며, 몇 개를 주문하더라도 배송비는 1번만 내면 된다.
공책 N개를 사는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

<입력>

첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어지며, 아래와 같은 형식으로 이루어져 있다.
각 테스트 케이스의
첫째 줄에 사려고 하는 공책의 개수 N과 쇼핑몰의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100, N ≤ Σsi)
M개의 줄에 si, pi, oi가 주어진다. (0 ≤ si, pi ≤ 10,000, 0 ≤ oi ≤ 1,000,000)

 

<출력>

각각의 테스트 케이스마다 민혁이가 공책 N개를 구매하기 위한 비용의 최솟값을 출력한다.

---

<접근 방식>

 

바로 전 포스트에 올린 간단한 배낭 2 문제와 거의 유사하지만, 같은 방식으로 접근하면 풀기 어려운 문제.

마찬가지로, 신촌 알고리즘 캠프 중급반 5주차 필수 문제 마지막 문제이다.

 

단순히 그리디한 DP로 접근하면, 각 테스트 케이스마다 O(NMS)의 시간 복잡도를 가져, 시간 초과를 겪게 된다.

 

배송비의 문제가 위의 문제의 접근을 어렵게 만드는데, 거꾸로 최적해부터 접근하면 생각보다 아이디어가 간단하다.

 

최적해의 경우, 공책을 구매할 쇼핑몰들은 고정되어 있다.. 물론 나는 모르지만

고정된 쇼핑몰들을 선택해서 배송비를 모두 지불하고 하면, 고려해야 하는 요소는 개수와 가격뿐이다. 

 

=> DP[i] : i개의 공책을 구매했을 때, 최소 비용

 

선택된 쇼핑몰들도 2가지로 나누어지는데

1. 모든 공책을 산 쇼핑몰

2. 모든 공책을 사지 못한 쇼핑몰 (현재 선택된 쇼핑몰 중 개당 최대 가격)

 

이렇게 2가지로 나누어지는 경우를 고려해서, 쇼핑몰들을 순회하면서, DP를 업데이트하면 최소 가격을 구할 수 있다.

 

<후기>

 

알고 보면 간단하지만, 혼자 고민하면서 풀려고 하니 굉장히 오래 걸렸다.. 

내가 보려고 만드는 블로그인 만큼 수시로 들어와서 과거 풀이들을 읽어보자