[C++] BOJ(백준) 20925 메이플스토리

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

20925번: 메이플스토리

 

DP 문제다.

 

시작점을 입력에 맞춰 체크해줘야 한다.

dp 배열은 시간과 위치로 설정했다.

 

dp 배열을 순회하면서 현재 경험치가 0인 곳은 스킵했다.

dp의 칸마다 움직일 수 있는 사냥터를 탐색하여 방학이 지나거나 경험치가 모자라는 경우를 제외했다.

 

이동하는 경우가 아닌 제자리에 머물러 있는 경우는 따로 고려를 했다.

 

#include <iostream>
#include <cstring>
using namespace std;

int dp[1001][200];
int t[200][200];
int c[200], e[200];
int n, m;

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	// 경험치 입력을 받으면서 입장에 필요한 경험치가 0인 곳 체크
	for (int i = 0; i < n; i++) {
		cin >> c[i] >> e[i];
		if (c[i] == 0) dp[0][i] = e[i];
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) cin >> t[i][j];

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			// 경험치가 없다면 continue
			if (!dp[i][j]) continue;

			for (int k = 0; k < n; k++) {
				// 방학 기간을 넘어서면 continue
				if (i + t[j][k] > m) continue;
				// 경험치가 입장에 필요한 최소 경험치보다 적으면 continue
				if (c[k] > dp[i][j]) continue;
				// 이동한거랑 안 한 거 중 어떤게 이득인지 판단
				dp[i + t[j][k]][k] = max(dp[i + t[j][k]][k], dp[i][j]);
			}

			// 1분 후 움직이지 않는 경우 따로 고려
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + e[j]);
		}
	}

	int re = 0;
	for (int i = 0; i < n; i++) re = max(re, dp[m - 1][i]);
	cout << re;
}

┗|｀O′|┛