글 읽기 - 1062(가르침) 1%에서 틀립니다.....반례좀 부탁드리겠습니다.

dnfwlq8054 3년 전 0

이거 관련된 반례들을 다 찾아봤는데 반례들은 다 맞더군요.

근데 1%에서 틀려서 무엇이 잘못되었는지 잘 모르겠습니다.

반례가 있다면 적어주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <random>
#include <map>
#include <stack>

#pragma warning(disable: 4996)

using namespace std;
int answer = 0;

void dfs(int idx, int k, vector<string>& v, int count, vector<bool> isCheck) {
	if (idx == v.size())
		return;

	vector<bool> cp_isCheck = isCheck;
	int cp_k = k;
	for (int i = 4; i < v[idx].size() - 4; i++) {
		if (!isCheck[v[idx][i] - 'a']) {
			isCheck[v[idx][i] - 'a'] = true;
			k--;
		}
	}
	if (k >= 0) {
		answer = max(answer, count + 1);
		dfs(idx + 1, k, v, count + 1, isCheck);
	}
	else {
		dfs(idx + 1, cp_k, v, count, cp_isCheck);
	}
}

int main() {
	int N, a, b, M, K;
	int sum = 0;
	vector<bool> isCheck(26);
	isCheck['a' - 'a'] = true;
	isCheck['n' - 'a'] = true;
	isCheck['t' - 'a'] = true;
	isCheck['i' - 'a'] = true;
	isCheck['c' - 'a'] = true;


	cin >> N >> K;
	vector<string> v(N);
	if (K < 5) {
		cout << 0 << endl;
		return 0;
	}

	string s;
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	K -= 5;
	for (int i = 0; i < v.size(); i++) {
		int count = 0;
		vector<bool> cp_isCheck = isCheck;

		for (int j = 4; j < v[i].size() - 4; j++) {
			if (!cp_isCheck[v[i][j] - 'a']) {
				count++;
				cp_isCheck[v[i][j] - 'a'] = true;
			}
		}
		if(K - count >= 0)
			dfs(0, K - count, v, 0, cp_isCheck);
	}

	cout << answer << endl;

	return 0;
}

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

문제

문제

출처

ICPC

1062(가르침) 1%에서 틀립니다.....반례좀 부탁드리겠습니다.

dnfwlq8054 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말