글 읽기 - 1062번 반례를 모르겠습니다.....

ohsh0731 5년 전 0

anta tica에 나오는 알파벳들 고정시키고, 나머지는 완전탐색으로 해서

동시에 되는 단어수가 최대가 되도록 해봤는데

밑에 질문들 테스트 케이스도 다 돌려보고 해도 맞게 나오는데 어디서 안되는지 모르겠습니다.

반례좀 도와주세요..

#include <bits/stdc++.h>
using namespace std;

const int asc = 'a';
int n,k;
char word[55][20];
bool alph[26];
int Wcnt = 0,ans = 0;

void sol(int cur, int num){
	if(cur > 26)return;
	if(num>=k){
		Wcnt = 0;
		for(int i = 0; i<n; i++){
			int length = strlen(word[i]);
			int cnt = 0;
			for(int j = 0; j<length; j++){
				if(alph[word[i][j]-asc])cnt++;
			}
			if(cnt == length)Wcnt++;
		}
		ans = max(ans,Wcnt);
		return;
	}
	if(cur == 'a'-asc||cur == 'n'-asc||cur == 't'-asc||cur == 'i'-asc||cur == 'c'-asc){
		sol(cur+1, num);
	}
	else{
		alph[cur] = 1;
		sol(cur+1,num+1);
		alph[cur] = 0;
		sol(cur+1,num);
	}
}

int main(){
	scanf("%d %d",&n,&k);
	for(int i = 0; i<n; i++){
		scanf("%s",word[i]);
	}
	alph['a'-asc] = 1;
	alph['n'-asc] = 1;
	alph['t'-asc] = 1;
	alph['i'-asc] = 1;
	alph['c'-asc] = 1;
	sol(0,5);
	printf("%d",ans);
	return 0;
}

rhs0266 5년 전 1

K의 범위를 다시 확인해보세요.

추가로, 현재 코드에서는 alph[26] 를 access 하는데 이를 수정해주려면 배열 크기를 27로 늘리거나 코드를 수정하면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

1062번 반례를 모르겠습니다.....

ohsh0731 5년 전 0

rhs0266 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말