PS/BOJ
[C++] 백준 1062번: 가르침 - Bitmask
__PS
2022. 11. 29. 17:57
728x90
https://www.acmicpc.net/problem/1062
1062번: 가르침
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문
www.acmicpc.net
비트연산자를 공부한 후 가장 처음 도전한 문제
배우고 응용은 처음이라그런지 상당히 코드는 더럽지만
그래도 어느정도 알겠다..
계속 틀린 이유는 k보다 v.size()가 작은 경우를 고려하지 않아서 틀렸고,
16번째 줄 구현이 너무 어려웠다.
내 생각에는 (1 << p) & t == (1 << p) 이런 느낌의 코드를 생각했으나 (포함 관계)
실제로는 계속 false가 반환되는 바람에 어디가 문제인지 찾지도 못했다.
더 공부해서 해당 부분을 다시 짜봐야겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string arr[51];
int n, k, ans, t;
bool check[26];
vector<char>v;
void track(int u, int cnt){
if(cnt==k || u==v.size()){
int res=0;
for(int i=0; i<n; i++){
bool c=true;
for(int j=0; j<arr[i].length(); j++){
int p=(arr[i][j]-'a');
if((1<<p)&t) continue;
else{
c=false;
break;
}
}
if(c) res++;
}
ans=max(ans, res);
return;
}
for(int i=u; i<v.size(); i++){
int l=v[i]-'a';
if(!check[l]){
check[l]=true;
t|=(1<<l);
track(i+1, cnt+1);
check[l]=false;
t&=~(1<<l);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> arr[i];
for(int j=0; j<arr[i].size(); j++) {
if(arr[i][j]!='a' && arr[i][j]!='n' && arr[i][j]!='t' && arr[i][j]!='i' && arr[i][j]!='c') v.push_back(arr[i][j]);
}
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
if(k<5){
cout << 0;
return 0;
}
t|=(1<<('a'-'a'));
t|=(1<<('n'-'a'));
t|=(1<<('t'-'a'));
t|=(1<<('i'-'a'));
t|=(1<<('c'-'a'));
check[0]=true;
check['n'-'a']=true;
check['t'-'a']=true;
check['i'-'a']=true;
check['c'-'a']=true;
track(0, 5);
cout << ans;
}
|
cs |