백준 29792번 규칙적인 보스돌이 (C++)

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

29792번: 규칙적인 보스돌이

 

- 접근법

 이 문제는 다이나믹 프로그래밍 배낭문제이다. 그러나 캐릭터 1,2,3이 있다고 할 때, 1,2,3마다 dp를 돌려서 마지막 최댓값을 모두 저장해놓고 답을 도출하면 된다.

 

가장 중요한 건 배낭문제를 잘 이해하고 있느냐는 것이다. 배낭문제를 복기해보자.

 

최대 10kg 담을 수 있고 물건은

번호  무게   가치

   1        4         6

   2        2         7

   3        5         3

   4        6         5

   5        8         7

위와 같이 정해져 있다고 하자 . 그리고 배낭문제의 정의에 따라, 2차원 배열을 선언하고 행에는 물건, 열에는 무게를 선언한다.

 

즉 dp[i][j] = i 번째 물건까지 도달했을 때 j 무게에서의 최대 가치이다. 

 

 

배낭 문제의 핵심은 한 행씩 채워가고 다음 행은 그 전 행의 메모를 보고 작성하게 된다. 이것을 메모이제이션이라한다.

1번 물건만을 가정한다고 하면 무게가 4가되었을 때 배낭에 넣을 수 있으므로 가치는 6이다. 그리고 이후에는 모두 6일것이다. 

 

이제 2번물건까지를 가정하자. 이제는 2번 물건도 넣을 수 있으므로 2kg까지일 때 7을 넣을 수 있다. 그리고 6kg까지 넣을 수 있을 땐 1,2를 모두 넣을 수 있으니 13이 최대 가치이다.

 

그리고 이제 점화식을 새워보면 

 

2번행의 6번째 즉, 2번 물건까지 살펴볼 때 6키로까지 담을 경우 최대 가치를 살펴보자.

 

dp[2][6] = dp[1][2] +가치

 

이것이 된다. 

 

그리고 더 통찰해보면 dp를 적어나가는 경우의 수는 다음과 같다.

1. 물건을 담을 수 없다.

2. 물건을 담을 수 있다.

 

위의 케이스는 2번이다. 그리고 담을 수 없다면 한 행의 위와 같다. 그러나 담을 수 있더라도 똑 담는것이 이득이라고 할 수 없다. 만약 2키로의 7가치 3키로의 2가치라면 3키로일 때 2키로 가치를 제거하는것 보다 그대로가는 것이 낫다.

 

즉 

 

if(담을 수 있다면) dp[i][j] = max( dp[i - 1][j] , dp[i - 1][j - 현재 무게] + 가치)

else dp[i][j] = dp[i - 1][j]

 

자 이제 이 문제로 다시 돌아와보자.

 

배낭문제라고 판단되었을 때 가장 중요한 것은 무엇이 무게에 해당하고 무엇이 가치에 해당하느냐이다.

이 문제에서 무게에 해당하는 것은 사냥시간이고 가치는 메소이다. 

 

1번 캐릭터의 공격력이 5라 하고 1번보스가 체력이 213, 메소는 50이라하자. 그렇다면 초당 공격력이 5이므로 사냥시간은 213 / 5 = 43초가 걸릴 것이다. 

 

그러므로 무게는 43

가치는  50이다. 

 

이제 배낭문제와 똑같이 진행하면 된다. 그리고 보스의 체력과 메소의 크기가 int를 벗어나기 때문에 long long으로 선언해줘야한다. 

 

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

map<int, long long> dps;
vector<pair<long long, long long>> bossinfo;
vector<long long> answer;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M, K;
	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		long long d;
		cin >> d;
		dps.insert({ i + 1, d });
	}

	for (int i = 0; i < K; i++) {
		long long hp, meso;
		cin >> hp >> meso;
		bossinfo.push_back({hp, meso});
	}

	for (int i = 0; i < N; i++) {
		long long thisdps = dps[i + 1];

		long long dp[14][901] = { 0, };
		for (int j = 1; j <= K; j++) {
			long long huntingTime = bossinfo[j - 1].first / thisdps;
			long long value = bossinfo[j - 1].second;

			if (bossinfo[j - 1].first % thisdps != 0) huntingTime++;

			for (int k = 1; k <= 900; k++) {
				if (k >= huntingTime)
					dp[j][k] = max(dp[j - 1][k], dp[j - 1][k - huntingTime] + value);
				else
					dp[j][k] = dp[j - 1][k];
			}

		}			
		answer.push_back(dp[K][900]);
	}

	sort(answer.rbegin(), answer.rend());
	long long ans = 0;
	for (int i = 0; i < M; i++) {
		ans += answer[i];
	}

	cout << ans << '\n';
}