[백준 1062번] 가르침 C++ 풀이

https://www.acmicpc.net/problem/1062

1062번: 가르침

 

 

문제 분석

N개의 단어가 주어지고, K개의 글자(알파벳)을 가르칠 수 있을 때

K개의 알파벳으로 배울 수 있는 글자 개수의 최대값을 구하는 문제.

이때 모든 글자는 "anta"로 시작되고, "tica"로 끝나기 때문에 가르칠 수 있는 K개의 글자엔 a, c, i, n, t가 포함되어 있다.

 

a부터 z까지 알파벳을 순회하면서 가르칠 수 있는 단어를 구하는 완전탐색이라고 생각했지만, 의외로 문제 풀이법(조합-재귀, 백트래킹)이 정형화된 문제인듯 하다.

완전탐색이지만 구현하는 데 있어 조합의 개념을 사용해야하는 문제.

 

 

문제 풀이

1. 가르친 알파벳을 저장하기 위해 a~z를 대표하는 0~26의 인덱스를 가진 배열 alpha을 만들어준다.

2. 이때 해당 배열 중 a, c, i, n, t는 무조건 가르쳐야하기 때문에 해당 인덱스의 값을 true로 바꾼다.

 

* 해당 배열을 통해 알파벳의 조합을 만든 뒤, 해당 알파벳 조합으로 단어를 만들 수 있는지, 만들 수 있는 개수가 무엇인지만 판단하면 되는 문제. 해당 코드에 대한 설명은 다음과 같다.

 

3. 조합을 담당하는 dfs함수의 인자엔 [지금 가르치는 알파벳 calpha]와 [지금까지 가르친 알파벳 개수 cnt]를 전달한다.

가르치지 않은 알파벳을 점점 늘리며 K개의 단어를 가르칠 때까지 dfs함수를 돌린다.

4. 만약 가르칠 수 있는만큼 알파벳의 조합을 만들었다면, 즉 cnt가 K-5개가 되었다면 이젠 해당 조합으로 가르칠 수 있는 단어가 있는지 확인한다. 모든 알파벳을 다 가르친 경우엔 단어를 학습한 것으로, isR이라는 flag가 true가 된다.

5. dfs 함수의 if문 안에 있는 for문을 돌면, K개의 조합으로 모은 알파벳으로 만들 수 있는 단어의 개수를 구할 수 있게 된다.

6. 모든 알파벳 조합에 대해 구할 수 있는 단어의 개수를 구한 뒤 최대값을 출력하면 된다.

 

DFS 함수의 코드는 기본적인 조합을 구현하는 코드로, 해당 글을 참고하면 좋다.

 

 

코드

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
int n,k,i,j,p,cnt,result,walpha;
bool isR;
string word[51];
string tmp;
bool alpha[26];
void dfs(int calpha, int cnt){
    // a, c, n, i, t를 제외한 가르칠 수 있는 K개의 알파벳을 다 가르친 경우
    if(cnt==k-5){
        walpha=0;
        for(i=0;i<n;i++){
            isR=true;
            for(j=0;j<word[i].size();j++){ 
                //단어의 알파벳 중 안 가르친 알파벳이 있다면 중단
                if(alpha[word[i][j]-'a']==false){
                    isR=false;
                    break;
                }
            }
            if(isR) {walpha++;} //모든 알파벳을 다 가르친 경우 -> 해당 단어는 가르친 것
        }
        result=max(result,walpha);
        return;
    }
    //알파벳을 순회하며 가르칠 알파벳에 대해 조합을 구해본다
    for(int c=calpha;c<26;c++){
        if(alpha[c]==true) continue;
        alpha[c]=true;
        dfs(c,cnt+1);
        alpha[c]=false; //다른 조합을 위해 검사를 완료한 알파벳은 false로 변경
    }
}
int main(){
    scanf("%d %d",&n,&k);
    for(i=0;i<n;i++){
        cin>>tmp;
        word[i]=tmp;
    }
    // k개 5개 미만이면 기본적인 알파벳 a, c, n, i, t을 가르칠 수 없다. -> 즉 가르칠 수 있는 단어가 없다
    if(k<5){
        printf("%d",0);
        return 0;
    }
    alpha['a'-'a']=true; 
    alpha['c'-'a']=true; 
    alpha['n'-'a']=true; 
    alpha['t'-'a']=true; 
    alpha['i'-'a']=true;
    dfs(0,0);
    printf("%d ",result);
    return 0;
}

 

 

마무리

string 배열을 만들고, 문자열은 cin으로 입력을 처리하면 좋다.

또한 문자를 숫자로 관리하고 싶을 땐 문자-'a'을 하면 된다.

조합을 재귀로 구현하는 법을 위의 알파벳을 관리하는 배열 관리법과 연결지으면 풀었을 수 있던 문제같다.

다른 블로그를 많이 참고했지만 다음에 비슷한 문제는 꼭 풀기.