반응형
1062번: 가르침
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문
www.acmicpc.net
|
1
2
3
4
5
6
7
8
|
// 백트래킹으로 사용하지 않은 문자 찾기
for (int i = now; i < 26; i++) {
if (!visited[i]) {
visited[i] = 1;
dfs(i + 1, cnt + 1);
visited[i] = 0;
}
}
|
cs |
|
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
|
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int visited[26];
vector<vector<char> > v;
int n, k, cnt = 5, ans;
string str;
void dfs(int now, int cnt) {
if (cnt == k) {
int temp = 0;
for (vector<char> vec : v) {
int j;
// 방문 안 한 글자 있으면 break
for (j = 0; j < vec.size(); j++)
if (!visited[vec[j] - 'a']) break;
// 끝까지 돌았으면 temp++
if (j == vec.size())
temp++;
}
ans = max(ans, temp);
return;
}
// 백트래킹으로 사용하지 않은 문자 찾기
for (int i = now; i < 26; i++) {
if (!visited[i]) {
visited[i] = 1;
dfs(i + 1, cnt + 1);
visited[i] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
v.resize(n);
// 앞 뒤 4글자 방문
visited['a' - 'a'] = 1;
visited['n' - 'a'] = 1;
visited['t' - 'a'] = 1;
visited['i' - 'a'] = 1;
visited['c' - 'a'] = 1;
// 가운데 글자 입력
rep(i,n){
cin >> str;
for (int j = 4; j < str.size() - 4; j++)
v[i].push_back(str[j]);
}
if (k < 5) {
cout << 0;
return 0;
}
dfs(0, cnt);
cout << ans;
}
|
cs |
반응형
'백준 > 백트래킹' 카테고리의 다른 글
| 백준 2580 (0) | 2021.02.24 |
|---|---|
| N-Queen 복습 (백준 9663) (0) | 2021.02.23 |
| 백준 16198 (0) | 2021.02.23 |
| 백준 15658 (0) | 2021.02.23 |
| 백준 1248 [복습 필수] (0) | 2021.02.15 |
