[BOJ/Gold 3] 백준 14628 입 챌린저(C++)

문제 링크

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

14628번: 입 챌린저

 

문제

광현이는 자칭 게임 아티스트이다. 게임 아티스트라고 해서 게임 캐릭터를 디자인하는 일이 아니라 게임을 Art하게 플레이하는 것을 의미한다. 광현이는 요즘 '리그오브스톰'이라는 게임에 빠졌다. 리그오브스톰은 스킬을 써서 상대방의 체력을 0 이하로 만들면 이기는 게임이다. 스킬은 총 N개가 있는데, 모든 스킬에는 사용 시 마나 포인트라는 비용이 필요하다. 또한, 스킬마다 상대방의 체력을 깎을 수 있는 수치가 정해져 있다. 스킬 사용 제한 횟수는 없지만 같은 스킬을 한 번 이상 사용할 때엔 필요한 마나 포인트가 원래 마나 포인트에서 K씩 추가로 증가한다. 예를 들어 어떤 스킬의 마나 포인트가 10이고 K값이 5이면 처음 사용할 때는 10, 그다음은 15, 그다음은 20 이런 식으로 증가하게 된다. 광현이는 이 게임을 아주 많이 플레이하여 브론즈 등급에 있었지만 슬슬 질려가고 있었다. 그래서 광현이는 게임 아티스트답게 플레이에 어떤 제약을 걸고 게임에 임하려고 한다. 그 제약이란 상대방의 체력을 정확하게 0으로 만들면서 마나 포인트를 최대한 적게 사용하는 것이다. 과연 광현이는 이 제약을 지킬 수 있을까? 광현이의 플레이가 맞는지 확인하기 위해 적의 체력을 정확하게 0으로 만들 때 필요한 가장 적은 마나 포인트를 구해보자.

입력

입력은 항상 적의 체력을 정확히 0으로 만들 수 있는 스킬의 조합만 들어온다. 첫째 줄에 스킬의 개수 N, 적의 체력 M, 같은 스킬을 사용할 때마다 추가되는 마나 포인트 K가 주어진다. (1≤N,M,K≤100) 둘째 줄부터 N개의 줄에 걸쳐서 한 줄마다 스킬에 필요한 마나 포인트 X와 상대방의 체력을 깎는 수치인 Y가 주어진다. (1≤X,Y≤100)

출력

첫째 줄에 적의 체력을 정확하게 0 으로 만들 때 필요한 가장 적은 마나 포인트를 출력한다.

예제 입력 1

3 95 5
1 3
5 10
10 35

예제 출력 1

85

알고리즘 분류

• 배낭 문제

풀이

이 분이 쓰신 글을 참고해서 해결하였다.

[ boj : 14628 ] 입 챌린저

스킬 사용 횟수에 제한이 없으므로, Unbounded 냅색 알고리즘을 사용해야 함을 알 수 있다.

DP[100][100]이라는 2차원 배열을 선언한다. 이것은 i번째 스킬까지 사용했을 때, j만큼의 체력을 깎았을 때 드는 마나 포인트의 최솟값을 의미한다.

그런데 스킬을 여러 번 사용할 때마다 K만큼의 마나 포인트를 추가로 소모해야 한다. 따라서

i번째 스킬을 한 번 사용했다면 X[i]만큼의 마나 포인트를 소모하지만,

두 번 사용했다면 X[i] + X[i] + K, 세 번 사용했다면 X[i] + X[i] + K + X[i] + K + K, 네 번 사용했다면 ....

이렇게 된다. N번 사용했다면 X[i]는 N번 나오고, K는 (N(N-1))/2번 나오는 것을 알 수 있다.

이것을 바탕으로 코드를 구현해서, 스킬을 사용해서 M만큼의 체력을 깎았을 때 드는 마나 포인트의 최솟값을 구하면 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 101
#define LL long long
#define INF 1e9

using namespace std;
int N, M, K;
int X[MAX], Y[MAX];
int DP[MAX][MAX];

void Init() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 1; j < MAX; j++) {
			DP[i][j] = INF;
		}
	}
}

void Input() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i];
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			for (int k = j / Y[i]; k >= 0; k--) {
				DP[i][j] = min(DP[i][j], DP[i - 1][j - k * Y[i]] + (X[i] * k) + (K * ((k * (k - 1)) / 2)));
			}
		}
	}
}

void Find_Answer() {
	cout << DP[N][M] << "\n";
}

int main() {
	FASTIO
	Init();
	Input();
	Settings();
	Find_Answer();

	return 0;
}