BOJ 5375 - 공책 구매

BOJ 5375 - 공책 구매

26969 풀이 와 동일하게 풀 수 있는데 좀 더 쉬운 버전이다.

$p_i$ 에대한 오름차순으로 정렬해둔다면 정답이 되는 쇼핑몰을 모두 골랐을 때 앞에서부터 $s_i$ 를 모두 꽉 채워서 사는것이 최적이다.

$dp[i][j]=i$ 번 째 서점 전까지 $j$개를 사는 최소값

으로 정의하고 반복문 DP로 푼다.

int dp[101][10001];  
const int inf = 0x3f3f3f3f;  
void solve() {  
   int n, m;  
   cin >> n >> m;  
   memset(dp, inf, sizeof dp);  
   vector<shop> s(m);  
   for (int i = 0; i < m; i++) cin >> s[i].s >> s[i].p >> s[i].o;  
   sort(all(s), [&](auto &a, auto &b) { return a.p < b.p; });  
   dp[0][0] = 0;  
   for (int i = 0; i < m; i++) {  
      for (int j = 0; j <= n; j++) {  
         if (dp[i][j] == inf) continue;  
         dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);  
         int buy = min(s[i].s, n - j);  
         dp[i + 1][j + buy] = min(dp[i + 1][j + buy], dp[i][j] + s[i].o + s[i].p * buy);  
      }  
   }  
   cout << dp[m][n] << endl;  
}