글 읽기 - 단순한 브루트포스아닌가요? 반례좀 찾아주세요 ㅠ

qktlf789456 3년 전 0

반례가 정말 필요합니다 ㅠ 예제는 너무 잘 나오고 오류가 없어보이는데요 ..

#include <iostream>
using namespace std;



struct node
{
	int from;
	int cost;
	char name[51];
};

char arr[20];
int n;

struct node book[20];

char used[20]{ 0, };
int total = 99999999;


char used_book[20]{ 0, };


void dfs(int idx, int sum, int cnt)
{
		
	if (sum >= total)
		return;

	if (arr[cnt] == NULL)
	{
		total = sum;


		return;
	}


	if(idx != -1)
		used_book[idx] = 1;


	for (int i = 0; i < n; i++)
	{
		if (used_book[i])
			continue;



		int used_cnt = 0;

		int used_idx[21]{ 0, };
		for (int j = 0; book[i].name[j]; j++)
		{
			for (int z = 0; arr[z]; z++)
			{
				if (used[z])
					continue;

				if (arr[z] == book[i].name[j])
				{
					used_idx[used_cnt++] = z;
					used[z] = 1;
				}
			}
		}

		if (used_cnt)
		{
			dfs(i, sum + book[i].cost, cnt + used_cnt);

			used_book[i] = 0;

			for (int j = 0; j < used_cnt; j++)
				used[used_idx[j]] = 0;
		}
	}


	if (idx != -1)
	{
		used_book[idx] = 0;
	}
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> arr >>  n;


	for (int i = 0; i < n; i++)
	{
		struct node key;
		cin >> key.cost >> key.name;

		int pre = i - 1;

		while (pre >= 0 && book[pre].cost < key.cost)
		{
			book[pre + 1] = book[pre];
			pre--;
		}

		book[pre + 1] = key;
	}



	dfs(-1, 0 , 0);


	if (total == 99999999)
		cout << -1;
	else
		cout << total;
	

	return 0;
}

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

문제

문제

출처

ICPC

단순한 브루트포스아닌가요? 반례좀 찾아주세요 ㅠ

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말