백준 1062 가르침

문제링크 : 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++)

#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;
}
 

문제유형

• 백트래킹 - 순열, 조합
  • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
  • 조합 : 리스트 마지막 다음부터 순회
  • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

• https://www.acmicpc.net/problem/15649
• https://www.acmicpc.net/problem/15650
• https://www.acmicpc.net/problem/15651
• https://www.acmicpc.net/problem/15652
• https://www.acmicpc.net/problem/15663
• https://www.acmicpc.net/problem/1062