글 읽기 - RPG 오답 ㅜㅜ 도와주세요

mrpjs21c 7년 전 0

정말 왠만해서 질문 안올리는데..ㅋㅋㅋ 이 문제는 정말 질문하게 되네요.

2차원 DP로 [힘][지식] 형태의 배열을 만들어서 구현했습니다.

i번째 퀘스트 깻을 때 능력치의 총합을 저장해두고, 거기서 힘을 뺀 만큼을 지식으로 간주하여, Bottom - Up DP 를 구현했습니다.

테스트 케이스 20개 정도 만들어서 돌려봤는데 ㅋㅋ 제 머리가 Boundary case를 잘 못찾는건지... 다 맞아도 제출하면 계속 오답이네요 ㅎㅎ

오답의 마수에 빠져버린 어린 양을 위해 잘못 이해한 부분이나 가이드 좀 부탁드립니다 ㅜㅜ

#include <iostream>

using namespace std;

#define max(a, b)		((a)>(b))?(a):(b)
#define min(a, b)		((a)>(b))?(b):(a)

typedef struct stats
{
	int st, in, pt;
};

int n = 0;
stats list[105];
int partition(stats* a, int p, int q)
{
	stats pv = a[p];
	int pv_min = min(a[p].st, a[p].in);
	int i = p, j = 0;
	for (j = p + 1; j < q; j++)
	{
		int j_min = min(a[j].st, a[j].in);
		if (j_min < pv_min)
		{
			i++;
			swap(a[i], a[j]);
		}
	}
	swap(a[i], a[p]);
	return i;
}
void quicksort(stats* a, int p, int q)
{
	int r = 0;
	if (p < q)
	{
		r = partition(a, p, q);
		quicksort(a, p, r);
		quicksort(a, r + 1, q);
	}
}

int dp[1005][1005] = { 0, };    //[힘][지식] 일 때 깰 수 있는 퀘스트 갯수의 최대값
int qsum[105] = { 0, };

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> list[i].st >> list[i].in >> list[i].pt;
	//순서가 상관없다면, 쉬운 퀘스트부터 수행한다.
	quicksort(list, 1, n + 1);

	//초기 str과 int의 총합은 2이며, 이를 i번째 퀘스트를 깬 후의 총합을 구해준다.
	qsum[0] = 2;
	for (int i = 1; i <= n; i++)
		qsum[i] = qsum[i - 1] + list[i].pt;

	dp[1][1] = 1;
	for (int i = 1; i <= n; i++)
	{
		//i번째 퀘스트를 수행
		for (int j = 1000; j >= 1; j--)
		{
			for (int k = list[i].pt; k >= 0; k--)
			{
				int next_s = j, next_i = qsum[i] - j;
				int prev_s = next_s - k, prev_i = next_i - (list[i].pt - k);

				//j가 i번째 퀘스트를 수행했을 때, str의 값이라면,
				//qsum[i] - j 가 i퀘스트를 수행했을 때, Int 값이 된다.
				if (prev_s <= 1000 && prev_i <= 1000
					&& prev_s >= 1 && prev_i >= 1
					 && dp[prev_s][prev_i] > 0)
				{
					if (next_i >= 1 && next_i <= 1000)
					{
						//만약 이전의 힘과 지식이 i번째 퀘스트를 깨기 충분하다면 깨고, 
						//next_s, next_i 만큼 스텟을 분배한다.
						if (prev_s >= list[i].st 
							|| (prev_i) >= list[i].in)
						{
							dp[next_s][next_i] = max(dp[next_s][next_i], 
													dp[prev_s][prev_i] + 1);

						}
					}
				}
			}
		}
	}

	int solve = 0;
	for (int i = 1; i <= 1000; i++)
		for (int j = 1; j <= 1000; j++)
			solve = max(solve, dp[i][j]);

	//초기에 퀘스트를 하나 깬 상태에서 시작하므로(1) 1을 빼준다.
	cout << solve - 1 << endl;
	int d = 0;
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

RPG 오답 ㅜㅜ 도와주세요

mrpjs21c 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말