[boj 6066] buying hay

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

6066번: Buying Hay

범위에 항상 유의하자!!

 

바텀업 디피 배열로 

 

dp[i] = Hay가 i를 만드는 최소한의 cost

를 계속 갱신해가면서 만들어나가면 된다.

각각의 dp배열은 정확히 그만큼의 hey를 만드는데 필요한 최소비용이므로,

H이상의 hey를 가지는 것중의 최소비용은 H이상의 dp배열을 돌면서 전부 따져줘야한다.

(정확히 말하면 새로갱신해 나갈때 쓰는  비용인 H_i가 5000이하이므로 M+5000이하까지만 따져주면 된다.)

 

needs to purchase H (1 <= H <= 50,000)에 꽃혀서 dp배열을 50001까지만 만들고, 50000까지만 도는 실수를 저질럿는데, 그러면 문제에서 원하는 모든경우를 구할 수없다 ㅠㅠ.

위에도 썻다싶이 각 배열은 정확히 그 가격을 만드는 경우만 저장하기 때문에 H가 50000일때, 사실 50001을 만드는 경우가 더 최소인 경우를 잡아 낼 수 없다.

그래서 다시 55001로 배열크기를 잡아서 맞출수 있었다.(차라리 백만정도로 잡아도 답은 맞았을 것이다.)

 

문제 조건과 범위를 유의해서 보도록하자

 

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX = 2e9;

typedef pair<int, int> pi;

int n, m;

int dp[55001];

int ans = 1e9;

int main() {

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

cin >> n >> m;

fill(dp, dp + 55001, (int)1e9);

dp[0] = 0;

vector<pi> v;

for (int i = 0; i < n; i++) {

int a, b;

cin >> a >> b;

v.push_back({ a,b });

}

for (int i = 0; i <= 55000; i++) {

if (i >= m)ans = min(ans, dp[i]);

for (auto j : v) {

if (i + j.first <= 55000) {

dp[i + j.first] = min(dp[i + j.first], dp[i] + j.second);

}

}

}

cout << ans;

}