글 읽기 - 41프로에서 계속틀립니당 ㅠㅠ 어디가 틀린지 모르겠어용

gktgnjftm 5년 전 0

k가 5일때 배울수있는 단어를 우선 전부다 체크를 해둬서 ans를 갱신시키고, 만약 k가 5초과면은 그냥 전부 다 돌리는 식으로 짜봤습니다. a n t i c를 미리 배우고 시작을 하여 최대의 경우 21Ck-5의 경우의수를 전부다 체크를 하여 따졌습니다.

temp는 a n t i c를 제외한 새로운글자를 넣는 벡터용이고, checkalpha는 그 글자가 체크가 되어있는지를 체크하는 용도입니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#include <string>
using namespace std;
int n, k,ans;
string aa[55];
bool visited[30];
int checkalpha[150];
vector<char> temp;
vector<char> temp2;
void go(int index,int cnt){
	if (index >=temp.size()+1) return;
	if (cnt == k){
		int ok = 0;
		for (int i = 0; i < n; i++) {
			string k = aa[i];
			bool no = false;
			for (int j = 0; j < aa[i].size(); j++) {
				char c = aa[i][j];
				if (checkalpha[c]) continue;
				else{
					no = true;
					break;
				}
			}
			if (!no) ok++;
		}
		ans = max(ans, ok);
		return;
	}
	for (int i = index; i <temp.size();i++){
		if (!visited[i]) {
			visited[i] = true;
			checkalpha[temp[i]] = 1;
			go(i+1,cnt + 1);
			visited[i] = false;
			checkalpha[temp[i]] = 0;
		}
	}
}
int main(){
	scanf("%d%d", &n, &k);
	// a n t i c 5개를 그냥 미리 배우고 시작 하자 ㅇㅇ
	for (int i = 0; i < n; i++) {
		cin >> aa[i];
		for (int j = 0; j < aa[i].size(); j++){
			char push = aa[i][j];
			if (push == 'a' || push == 'n' || push == 't' || push == 'i' || push == 'c') {
				checkalpha[push] = 1;
				continue;
			}
			temp.push_back(aa[i][j]);
		}
	}
	if (k < 5) {
		printf("0\n");
		return 0;
	}
	k -= 5;
	sort(temp.begin(), temp.end());
	temp.erase(unique(temp.begin(),temp.end()),temp.end());
	if (temp.size() == 0) {
		printf("%d\n", n);
		return 0;
	}
	if (k == 0){
		int ok = 0;
		for (int i = 0; i < n; i++){
			string k = aa[i];
			bool no = false;
			for (int j = 0; j < k.size(); j++) {
				char next = aa[i][j];
				if (checkalpha[next]) continue;
				else {
					no = true;
					break;
				}
			}
			if (!no) ok++;
		}
		ans = max(ans, ok);
	}
	for (int i = 0; i < temp.size(); i++)
	{
		visited[i] = true;
		checkalpha[temp[i]] = 1;
		go(i+1,1);
		visited[i] = false;
		checkalpha[temp[i]] = 0;
	}
	printf("%d\n", ans);
	return 0;
}

djm03178 5년 전 17

반례 드립니다.

1 7
antabbtica
output: 0
correct answer: 1

2 7
antaatica
antabtica
output: 0
correct answer: 2

1 7
antabctica
output: 0
correct answer: 1

gktgnjftm 5년 전 0

오 감사합니다 우선해보겠습니당

gktgnjftm 5년 전 0

감사합니다 덕분에 해결했습니다 ^^ 애초에 다 배우기 이전에도 단어의 갯수의 경우를 구해야 하는걸 깜빡했습니다. 그러면 일일이 다 비교해서 시간초과날거같았는데 간신히 통과했습니다 감사합니당

hejh6408 5년 전 0

감사합니다. 저도 덕분에.^^

jksk0115 4년 전 0

djm03178 님 덕분에 뭐가 틀렸는지 알 수 있었네요. 감사드립니다.

yoonjechoi 4년 전 0

하악 하악 저도 덕분에 41%에서 계속틀렸는데 맞았습니다!!!!!!!

감사합니다.

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

문제

문제

출처

ICPC

41프로에서 계속틀립니당 ㅠㅠ 어디가 틀린지 모르겠어용

gktgnjftm 5년 전 0

djm03178 5년 전 17

gktgnjftm 5년 전 0

gktgnjftm 5년 전 0

hejh6408 5년 전 0

jksk0115 4년 전 0

yoonjechoi 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말