글 읽기 - 붕어빵 문제 계속 10%에서 틀립니다.

ray_lucid 5년 전 0

저는 백트래킹 방식으로 접근을 하였는데요,

우선 가성비로 정렬을 한 후 DFS로 탐색하면서 leaf 노드에 도달하면

best 값을 갱신하고, 만약 기대치가 best 보다 못하다면 더 탐색하지 않는 식으로

진행을 하였습니다. 테스트 케이스를 전부 통과하였고 질문 게시판에 올라온 모든 반례를

다 통과하였는데 어느 부분에서 문제가 있는지 모르겠습니다.

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

struct profit
{
	profit(){}
	profit(int n, int a, float u) :number(n), amount(a), unitprofit(u){}
	int number;
	int amount;
	float unitprofit;

	bool operator<(profit p) const
	{
		return this->unitprofit > p.unitprofit;
	}
};
vector<profit> v;
int N = 0;
int best = 0;
int Prediction(int n)
{
	int point = 0;
	int Sum = 0;
	while (n > 0)
	{
		if (n - v[point].number >= 0)
		{
			Sum += v[point].amount;
			n -= v[point].number;
		}
		else
			point++;
	}
	return Sum;
}
void DFS(int n, int Sum)
{
	int remain = n;
	if (n == 0)
	{
		if (Sum > best)
			best = Sum;
		return;
	}
	else
	{
		if (Sum + Prediction(n) <= best)
			return;
		for (int i = 0; i < N; i++)
		{
			if (remain - v[i].number >= 0)
			{
				int next = Sum;
				next += v[i].amount;
				DFS(remain - v[i].number, next);
			}
		}
	}
}
int main(void)
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int a; float u;
		cin >> a;
		u = (float)a / i;
		v.push_back(profit(i, a, u));
	}
	sort(v.begin(), v.end());
	DFS(N, 0);
	cout << best << endl;
	return 0;
}

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

문제

문제

출처

ICPC

붕어빵 문제 계속 10%에서 틀립니다.

ray_lucid 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말