1062번: 가르침
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.
www.acmicpc.net
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 |