STL 공부하면서 배운거좀 써먹어보겠다고 까불다가 이틀동안 고생한 문제..
for_each 함수로 입력받은 단어에서 anta, tica 를 제외한 나머지 단어를 검사해서 가르칠 횟수가 남아있고, 아직 배우지 않은 알파벳이라면 alpha 문자열에 추가하는 식으로 구현했는데, 알파벳 하나하나 검사하는 것이 아닌 입력받은 단어 순서대로 검사하게되어 반례가 존재하는 구현이었다...ㅜ ㅜ 다른 사람들의 구현을 보고 모든 알파벳에서 남극언어(a,n,t,i,c)를 다 배운다는 가정하에 배울 수 있는 모든 경우의 수를 구하는 방향으로 다시 구현하였다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> voca;
bool alpha[26];
int maxLearn, n, maxCnt = 0;
void Solution(int start, int pick)
{
if (pick == maxLearn) // 다 가르쳤다면
{
int cnt = 0;
for (int i = 0; i < n; i++)
{
bool check = true;
for (string::size_type j = 0; j < voca[i].size(); j++)
{
if (alpha[voca[i][j] - 'a']) continue;
check = false;
break;
}
if (check) cnt++;
}
maxCnt = max(maxCnt, cnt);
return;
}
for (int i = start; i < 26; i++)
{
if (alpha[i]) continue;
alpha[i] = true;
Solution(i + 1, pick + 1);
alpha[i] = false;
}
}
int main(void)
{
cin >> n >> maxLearn;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
voca.push_back(str);
}
if (maxLearn < 5)
{
cout << 0 << endl;
return 0; // antic
}
else if (maxLearn == 26)
{
cout << n << endl;
return 0;
}
alpha['a' - 'a'] = true;
alpha['n' - 'a'] = true;
alpha['t' - 'a'] = true;
alpha['i' - 'a'] = true;
alpha['c' - 'a'] = true;
maxLearn -= 5;
Solution(1,0);
cout << maxCnt << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 24day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1213번: 팰린드롬 만들기 (0) | 2020.04.30 |
---|---|
백준 2981번: 검문 (0) | 2020.04.30 |
백준 6679번: 싱기한 네자리 숫자 (0) | 2020.04.28 |
백준 1074번: 게임 (0) | 2020.04.28 |
백준 7453번: 합이 0인 네 정수 (0) | 2020.04.26 |