[ boj : 14628 ] 입 챌린저

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

14628번: 입 챌린저

해설 : 문제를 이해하는건 어렵지 않습니다. 다만 점화식을 세우는 것이 너무나도 까다롭더라구요....

여러개의 스킬을 조합해야 하고, 스킬을 사용할 수 있는 제한이 존재하지 않는 것을 통해

unbounded knapsack 문제라고 판단이 들었고 그렇게 점화식을 세웠습니다. 다만 평소에 풀어본 unbounded knapsack 문제는 1차원 배열로 해결하였는데, 1차원으로는 세워지질 않아서 그냥 2차원으로 선언해서 풀었습니다.

 

dp[i][j] = i번째 스킬까지 사용하였을때, j 만큼 hp를 깍을 수 있는 마나의 최소값

 

스킬을 1번째 사용하였을때 : x

스킬을 2번째 사용하였을때 : x + (x+k)

스킬을 3번째 사용하였을때 : x + (x+k) + (x+x+k+x+k+k)

스킬을 4번째 사용하였을때 : x + (x+k) + (x+x+k*1+x+k*2+x+k*3)

 

규칙성을 찾을 수 있겠죠?

i번째 동일한 스킬을 사용한다고 하면 x는 i 번, k는 (i*(i-1))/2 번 반복되서 나옵니다.

이를 잘 구현해주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int dp[110][110];

void solve();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	int n, m, k;

	cin >> n >> m >> k;
	vector<pair<int, int>> v(n+1);
	for (int i = 0; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = (int)1e9;
	for (int i = 1; i <= n; i++)
		cin >> v[i].first >> v[i].second;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int p = j / v[i].second; p >= 0; p--)
				dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i].second * p] + v[i].first * p + k * ((p * (p - 1)) / 2));
	cout << dp[n][m];
}