백준 25216 - 파밍 루트(C++)

문제 링크입니다. https://www.acmicpc.net/problem/25216

25216번: 파밍 루트

그래프 탐색과 Dp가 섞여있는 문제입니다.

1번 던전부터 시작해서 T시간이 걸릴 때까지 연결된 다른 지점을 방문해 최대 코인을 얻을 수 있는지 구하는 문제입니다.

최대 코인을 얻을 수 있는 곳에서의 필요한 방어력의 값을 구해야 합니다.

 

먼저, 같은 X지점을 방문했다고 해도 방문한 시간이 다르다면 서로 다른 경우로 봐야합니다.

따라서 지점과 시간을 동시에 저장해주기 위해 2차원 배열을 사용해주면 됩니다.

 

X시간, Y지점에서 필요한 방어력을 구해야합니다.

체력이 닳으면 안되기에  a+xt-yd 에서 yd가 a+xt보다 크거나 같아야합니다. 이에 따라서 방어력을 구해줍니다.

 

X시간, Y지점에서 최대 코인 값을 구하기 위해선 DP를 이용했습니다.

1. 해당 시간, 지점을 이전에 방문한 적이 없는 경우 -> 현재 경우에서 다음 지점의 코인 값을 더해줍니다.

2. 해당 시간, 지점을 방문했던 경우

   2-1. 현재 경우가 저장된 값보다 더 큰 경우 -> 현재 경우의 값으로 바꿔줍니다.

   2-2. 현재 경우와 같은 경우 -> 방어력을 통해 비교해줍니다.

 

이에 따라서 그래프를 탐색하면서 dp 배열의 값을 바꿔줍니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define LL long long

using namespace std;

typedef struct mon{ //몬스터 정보를 저장하기 위한 구조체
	LL a;
	LL x;
	LL y;
	LL c;
}mon;
mon monster[5001];
vector<int> portal[5001];  // X번 포털과 연결된 포털들을 저장
LL dp[110][5001]; // 모은 코인의 수
LL demage[110][5001]; // X시간, Y지점에서 필요한 방어력
int N, M, T;

int get_defense(int x, int time_){ // 해당 시간과 지점에서 필요한 방어력을 구하는 함수
	LL Demage = monster[x].a + monster[x].x * time_;
	if(Demage % monster[x].y == 0) return Demage / monster[x].y;
	else return Demage / monster[x].y + 1;
}

void bfs(int start){ // 1번 지점부터 시작해 연결된 지점들을 방문하는 함수
	queue<P> q; // 시작한 위치 & 걸린 시간
	q.push({1,1});	
	demage[1][1] = get_defense(1, 0); // 처음방문한 1번 지점에서 필요한 방어력
	dp[1][1] = monster[1].c; // 해당 시간, 지점에서의 최대 코인값
	while(!q.empty()){
		int x = q.front().first;
		int time_ = q.front().second;
		LL defense = demage[time_][x];
		q.pop();
		if(time_ > T) continue; // 제한 시간이 끝나면 확인X
		for(int i = 0; i < portal[x].size(); i++){
			int xx = portal[x][i];
			LL new_defense = get_defense(xx, time_) > defense ? get_defense(xx, time_) : defense;
			if(dp[time_ + 1][xx] == 0){ // 해당 시간, 지점이 방문하지 않은 곳이였다면
				dp[time_ + 1][xx] = dp[time_][x] + monster[xx].c; // 이전 방문했던 곳+현재 지점의 코인 수가 최대
				demage[time_ + 1][xx] = new_defense; // 최대 방어력 저장
				q.push({xx,time_ + 1});  // 다음 지점을 탐색하기 위해 저장
			}
			else if(dp[time_ + 1][xx] < dp[time_][x] + monster[xx].c){ // 현재 경우가 더 코인이 많을 때
				dp[time_ + 1][xx] = dp[time_][x] + monster[xx].c;  
				demage[time_ + 1][xx] = new_defense;
				q.push({xx,time_ + 1});
			}
			else if(dp[time_ + 1][xx] == dp[time_][x] + monster[xx].c){  // 현재 경우와 같을 때는 방어력으로 비교
				if(demage[time_ + 1][xx] > new_defense){
					demage[time_ + 1][xx] = new_defense;
					q.push({xx, time_ + 1});
				}
			}
		}
	}
}

void solve(){
	bfs(1);
	P Max = {0,0}; // 시간, 구역
	LL maxi = 0;
	for(int i = 1; i <= T; i++){ // 최대로 코인을 얻을 수 있는 곳을 찾는다.
		for(int j = 1; j <= N; j++){
			if(maxi < dp[i][j]){
				maxi = dp[i][j];
				Max = {i,j};
			}
			else if(maxi == dp[i][j]){ // 코인이 같다면 방어력으로 비교
				if(demage[Max.first][Max.second] > demage[i][j]){
					maxi = dp[i][j];
					Max = {i,j};
				}
			}
		}
	}
	cout << demage[Max.first][Max.second];
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> T;
	for(int i = 1; i <= N; i++){
		mon x;
		cin >> x.a >> x.x >> x.y >> x.c;
		monster[i] = x;
	}	
	for(int i = 1; i <= M; i++){
		int x, y;
		cin >> x >> y;
		portal[x].push_back(y);
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요