문제링크 : https://www.acmicpc.net/problem/1062
아이디어
- 26개중에 K개 알파벳을 고를때 (백트래킹 조합),
- N개의 문자열이 모두 통과하는지 확인
- 최대 값을 구하는 문제이므로 모든 경우의 수에서 다 해보자
시간복잡도 계산
- 백트래킹 O(N^N)
- anta, tica에서 5개는 고정
- 백트래킹으로 20개중 최대 20개 고를떄 > 20^20 > 시간초과
- 그치만, 가지치기를 예상해서 한번 해보자.
자료구조
- 문자열 리스트 : vector
- 백트래킹 리스트 : vector
- 리스트 내부 최대값 26이므로 가능
- 알파벳 중복 체크 : bool[26]
코드(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 | #include <iostream> #include <string> #include <vector> using namespace std; vector<string> s; bool chk[26]; int N,K; int maxv = 0; vector<int> v; void dfs(int num) { // 5개 제외하고 모두 고를경우 if(num == K-5) { int cnt=0; for(string es : s) { bool sw = false; for(int i=0; i<es.size(); i++) { char ec = es[i]; if(chk[ec-'a'] == false) { sw = 1; break; } } if(sw==false) cnt++; } maxv = max(maxv, cnt); return; } // 알파벳 중복체크 후 추가 // 조합이므로 리스트 맨 뒤에서 빼기 int lastv = -1; if(!v.empty()) lastv = v.back(); for(int i=lastv+1; i<26; i++) { if(chk[i]) continue; chk[i] = 1; v.push_back(i); dfs(num+1); chk[i] = 0; v.pop_back(); } } int main() { ios::sync_with_stdio(0); cin.tie(0); fill(chk, chk+26, 0); cin >> N >> K; // 문자열 잘라서 보관 for(int i=0; i<N; i++) { string es; cin >>es; // 잘라서 보관 s.push_back(es.substr(4,es.size()-8)); } chk['a'-'a'] = 1; chk['n'-'a'] = 1; chk['t'-'a'] = 1; chk['i'-'a'] = 1; chk['c'-'a'] = 1; // 5개 이하일경우 문자열 읽을 수 없음 if(K<5) { cout << 0 << '\n'; return 0; } dfs(0); cout << maxv << '\n'; return 0; } | cs |
문제유형
- 백트래킹 - 순열, 조합
- 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
- 조합 : 리스트 마지막 다음부터 순회
- 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김
비슷한 문제
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 14719 빗물 (0) | 2021.03.17 |
|---|---|
| 백준 14499 주사위 굴리기 (0) | 2021.03.17 |
| 백준 9663 N-Queen (0) | 2021.03.16 |
| 백준 2293 동전 1 (0) | 2021.03.16 |
| 백준 15663 N과 M (9) (0) | 2021.03.15 |