반응형
1062번: 가르침
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문
www.acmicpc.net
알고리즘 종류
완전탐색
사고 과정
읽을 수 있는 최대 단어의 개수를 찾아야 합니다. 시작 글자와 끝 글자를 제외하고 중간에 남는 글자들에서 중복을 제외해야 한다고 생각했습니다. 그리고 a~z중에서 k-5개를 선택해서 남은 글자들을 커버할 수 있는지 확인하면 될 것 같습니다. k가 5미만이면 무조건 0개의 단어를 읽을 수 있습니다.
1. 기본으로 선택된 글자들은 미리 선택되게 합니다. 그리고 DFS를 이용한 조합으로 a~z 중에 k-5개를 선택합니다.
2. 가공된 입력 단어를 가져옵니다. 그리고 for문으로 돌면서 조합으로 선택된 글자로 커버가 되는지 확인합니다.
3. 커버가 되는 단어의 개수를 세어서 최대 개수를 갱신합니다.
구현(C++)
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int n, k;
int ans=0;
int isSelected[26];
map<char, int> dict;
vector<char> words[51];
vector<char> v;
// 선택된 글자로 읽은 수 있는 단어 세기
void check(){
int cnt = 0;
for(int i=1; i<=n; i++){ // bring a word
bool flag = true;
for(int j=0; j<words[i].size(); j++){
char c = words[i][j];
if(!isSelected[c - 'a']) {
flag = false;
break;
}
}
if(flag) cnt++;
}
ans = max(cnt, ans);
}
// 조합으로 글자 선택
void dfs(int idx, int cnt){
if(cnt == k-5){
check();
return;
}
for(int i=idx; i<26; i++){
if(isSelected[i]) continue;
isSelected[i] = 1;
dfs(i, cnt+1);
isSelected[i] = 0;
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
if(k < 5) {
cout << 0 << "\n";
return 0;
}
string str;
// 앞 뒤 글자 제거하고, 중복 제거
for(int i=1; i<=n; i++){
cin >> str;
dict.clear();
for(int j=4; j<str.length()-4; j++){
char c = str[j];
if(dict[c]) continue;
words[i].push_back(c);
dict[c] = 1;
}
}
// 기본 글자 표시
isSelected['a' - 'a'] = 1;
isSelected['c' - 'a'] = 1;
isSelected['i' - 'a'] = 1;
isSelected['n' - 'a'] = 1;
isSelected['t' - 'a'] = 1;
dfs(0, 0);
cout << ans << "\n";
}
|
cs |
시행착오
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
[백준][C++] 9081 단어 맞추기 (0) | 2021.04.20 |
---|---|
[백준][C++] 18119 단어 암기 (0) | 2021.04.20 |
[백준][C++] 1941 소문난 칠공주 (0) | 2021.04.19 |
[백준][C++] 3687 성냥개비 (0) | 2021.04.19 |
[백준][C++] 11437 LAC(lowest Common Ancester) (0) | 2021.04.19 |