글 읽기 - 8%에서 틀림.. 어디가 문제일까요

sbslc2000 2년 전 0

이것 저것 반례를 찾아보려 해도 잘 찾아지지 않네요

#include <iostream>
#include <vector>
using namespace std;
int INFI = 21000000;

//기준치
int mp;
int mf;
int ms;
int mv;

int N;

//완전탐색시 사용할 벡터
vector<int> picked;

//정답을 저장해놓을 벡터
vector<int> answer;
// row 0: 단백질 1:지방 2:탄수화물 3:비타민 4:가격
int table[15][5];

int minCost = INFI;

void copyVec()
{
	answer.clear();
	for(int i=0; i<picked.size(); i++)
	{
		answer.push_back(picked[i]);
	}
}

int getCost()
{
	int ret = 0;
	for(int i=0; i<picked.size(); i++)
	{
		ret += table[picked[i]][4];
	}
	return ret;
}

bool isSatisfied()
{
	int sump=0, sumf=0, sums=0, sumv=0;
	for(int i=0; i<picked.size(); i++)
	{
		sump += table[picked[i]][0];
		sumf += table[picked[i]][1];
		sums += table[picked[i]][2];
		sumv += table[picked[i]][3];
	}

	if(sump >= mp && sumf >=mf && sums >=ms && sumv >= mv)
	{
		return true;
	}
	else
	{
		return false;
	}
}
void pickIngredient(int toPick)
{
	if(toPick == 0) // 다 골랐을때
	{
		if(isSatisfied()) // 기준량 이상을 섭취할 수 있으면
		{
			int cost = getCost();
			if(cost < minCost) // 새 방법이 기존의 방법보다 비용이 작다면
			{
				copyVec(); // 고른 식재료를 answer에 저장
				minCost = cost;
			}
			return;
		}
		
		return;
	}
	
	int least;
	if(picked.size() == 0)
	{
		least = 0;
	}
	else
	{
		least = picked.back()+1;
	}
	
	for(int i=least; i<N; i++)
	{
		picked.push_back(i);
		pickIngredient(toPick - 1);
		picked.pop_back();
	}
}

void init()
{
	cin >> N;
	cin >> mp >> mf >> ms >> mv;
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<5; j++)
		{
			cin >> table[i][j]; 
			
		}
	}
	
}

int main() {
	init();
	for(int i=1; i<=N; i++)
	{
		//i개를 고르는 경우의 수를 탐색
		pickIngredient(i);
	}
	
	//조건에 부합하지 않는다면 ( isSatisfied가 false만 return 한 경우)
	if(minCost == INFI)
	{
		cout << -1;
		return 0;
	}
	else //조건에 부합한 경우
	{
		cout << minCost << endl;
		for(int i=0; i<answer.size(); i++)
		{
			cout << answer[i]+1 << ' ';
		}
	}
	return 0;
}

euphoric_n 2년 전 4

반례 드립니다. (게시글에 이미 있습니다.)

input :

0 0 0 1

0 0 0 0 0

0 0 0 1 0

output :

answer :

1 2 3

사전순으로 앞서는 것을 출력해야합니다.

sbslc2000 2년 전 0

euphoric_n

일반적으로 3 과 1 2 3 이 있을때 1 2 3 이 사전순으로 더 앞서는 건가요? 원소 수가 적은게 사전순으로 앞선줄 알았는데 아닌가보네요 ㅜ 답변감사드립니다.

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

문제

문제

출처

ICPC

8%에서 틀림.. 어디가 문제일까요

sbslc2000 2년 전 0

euphoric_n 2년 전 4

sbslc2000 2년 전 0

euphoric_n

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말