[백준] 25216번 파밍루트 [C++]

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

25216번: 파밍 루트

---

문제

---

접근 방법

 

우선 방어력에 초점을 두지 말고, 내가 구할 수 있는 가장 많은 금화의 양을 계산을 해야한다. 방어력을 max값으로 두고,어느 지점에서도 막히지 않게 한다면 주어진 시간동안 구할 수 있는 가장 많은 금화를 구할 수 있다.

이는 다이나믹 프로그래밍 방법으로 구하게 됐는데,

 

DP[남은 시간][현재 위치]=max(DP[남은시간 - 1][현재 위치에서 갈 수 있는 곳])+현재 위치에서 얻을 수 있는 금화의 양

이라는 식을 생각할 수 있다.

 

이해가 어려워서 예시를 들자면 현재 내가 2초가 남았고, 내가 갈 수 있는곳이 (2)번과 (3)번이라면,

지금 내 위치에서 가장 많이 구할 수 있는 금화의 양은 1초 남은 (2)번과 (3)번중에서 더 높은 금화를 얻을 수 있는 곳 + 현재 위치에서 구한 금화의 양

이라는 뜻이 된다.

 

이러한 방법으로 금화의 최대값을 구하고, 그 후에 이분탐색을 사용해 방어력 값을 구하였다.

내가 입는 데미지가 1이라도 되면 게임 오버기 때문에, 문제에 쓰여있는 공식처럼

몬스터의 기본공격력+ 시간당 공격력 증가량*경과한 시간 - 방어력당 공격력 감소량*방어력의 값이 0보다 크다면 게임 오버기 때문에 무조건 반환값을 0이라고 생각을 한다.

이러한 식을 짠 후, 이분탐색으로 방어력 값을 조정을 한다면

현재 방어력으로 얻을 수 있는 금화 = 미리 구한 최대 금화 의 공식을 이용해 방어력의 최소도 구할 수 있다.

 

주의사항)

데미지 계산 식에 경과한 시간이라는 변수가 있는데, 우리가 dp를 할 때에는 남은 시간을 기준으로 계산을 하였기 때문에, 경과한 시간은 그냥 시간을 곱해주면 안되고 (전체 시간 - 남은 시간)으로 계산을 해줘야 한다.

 

---

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<tuple>
#include<vector>
using namespace std;
int dp[101][5001];
vector<int> v[5001];
vector<int> rv[5001];
tuple<int, int, int, int> monster[5001];
int n, m, ti;
int dpf(int t, int cur,long long def) {	
	if (t == 0) {
		return 0;
	}
	if (get<0>(monster[cur]) + (ti-t) * get<1>(monster[cur]) - get<2>(monster[cur]) * def > 0)
		return 0; //위에서 언급한 게임오버
	if (dp[t][cur] != -1)return dp[t][cur];
	int maxi = get<3>(monster[cur]);
	for (int i = 0; i < v[cur].size(); i++) {	
		maxi = max(maxi, dpf(t - 1, v[cur][i],def) + get<3>(monster[cur]));
	}
	dp[t][cur] = maxi;
	return maxi;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> ti;
	for (int i = 1; i <= n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d  ;
		monster[i] = { a,b,c,d };
		for (int j = 1; j <= ti; j++)dp[j][i] = -1;
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		rv[y].push_back(x);
	}
	int maxi = dpf(ti, 1, 2000000000); //넣는 방어력의 최대값을 20억이라고 가정
	long long s = 0;
	long long e = 2000000000;
	while (s <= e) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= ti; j++)dp[j][i] = -1; //dp배열을 초기화 해줘야 한다.
		}
		long long mid = (s + e) / 2;
		if (dpf(ti, 1, mid) == maxi) {	//현재 방어력으로 최대 금화를 얻을 수 있다면 값을 내려준다.
			e = mid - 1;
		}
		else { //얻을 수 없다면 올려준다.
			s = mid + 1;
		}
	}
	cout << s;
}

---

대회에서 문제를 처음 보고, 어마어마한 텍스트량에 압도돼서 넘어갔던 문제였다. 알고보니 못 푼 문제중에서는 가장 도전해봄직하지 않았나 라고 생각이 든다.

문제를 풀면서 헷갈렸던 점은 (1) 방어력의 최댓값, (2)위에서 언급한 경과시간과 남은시간 이었다.

계속해서 dp의 시간값을 경과시간이라고 생각하면서 문제를 풀었는데, 결과가 좋지 않아서 대회 해설을 보니 남은시간으로 하라고 되어있어서. . . 이 부분에서 조금 막혔었다.