[백준 c++] 1062 가르침 (골4)

📌 문제

항상 문제에서 애매하게 설명하기 때문에 예시를 보면 좀 더 명확하게 문제를 이해하는 듯 하다.

많은 단어를 읽을 수 있도록하되, 알파벳 K개의 글자를 가르쳐 이때 읽을 수 있는 단어의 최대 개수를 출력하는 문제였다.

 

문자열 다루기 + 백트래킹 + brute force였다.

 

조건 1) 알파벳 몇 개를 가르칠 것인가?

먼저 "anta" ~ "tica"는 무조건 읽을 수 있어야 모든 단어를 읽을 수 있는 기회(?)가 주어지기 때문에,

"atinc"는 무조건 읽어야한다. 그러므로, 알파벳을 선택하는 배열에 "atinc"는 디폴트로 선택할 수 있도록 한다.

 

이렇게 되면, 처음 시작할 때부터 5개의 알파벳을 선택하고 시작해야한다. 

그말은, 알파벳 배우는 개수인 K개가 5개보다 적으면 애초에 아무런 단어를 배울 수 없다는 뜻.

그 조건을 추가한다.

 

알파벳을 선택하는 경우의 수를 탐색하기 위해 백트래킹 함수인 chooseRecursive(int least, int alphaIdx)를 활용했다.

 

보통 백트래킹을 구현할 때, stack 자료구조를 활용해서 구현한다.

근데, 선택을 해야하는 경우와 몇 개의 단어를 읽을 수 있는지 확인해야하는 상황이기 때문에

작업을 분할할 수 있도록 함수로 만드는 것이 좋겠다 싶어 재귀함수로 풀었다...

 

가끔 시간초과로 인해 재귀 함수로 백트래킹 문제를 풀 수 없는 경우도 있기 때문에

재귀보다는 일단 stack, queue 자료구조를 활용해서 구현하려고 노력하는 편이다. 하지만 재귀함수가 아무래도 직관적이고 구현하기 쉽긴하다...

 

조건2) 배운 알파벳으로 몇 개의 단어를 읽을 수 있는가?

각 단어 별로 알파벳을 확인하여 몇 개의 단어를 읽을 수 있는지 말그대로 하나씩 확인하고 최댓값인지 확인하는 함수이다

brute force.

 

 

💻 정답 코드

#include <iostream>
using namespace std;

string words[50];
int N, K;
int learnMax;
bool alphaCheck[26];

void countLearnWords(){
    
    int wordCnt = 0;
    //N개의 알파벳에서 계산
    for(int i = 0; i < N; i++){
        
        int canRead = true;
        
        //앞, 뒤 알파벳 제외 중간알파벳을 읽을 수 있는 지 여부 확인하기
        for(int j = 4; j < words[i].size() - 4; j++){
            
            int alphaNum = (int)(words[i][j] - 'a');
            if(alphaCheck[alphaNum] == false){
                canRead = false;
                break;
            }
        }
        
        //읽을 수 있는 단어라면, 추가
        if(canRead == true) wordCnt++;
    }
    
    //최대인지 확인
    if(wordCnt > learnMax) learnMax = wordCnt;
    
}

void chooseRecursive(int least, int alphaIdx){
    
    //더이상 남은 알파벳이 없을 경우 + 다 선택시, 사용 가능한 단어들 확인하기
    if(alphaIdx > 25 || least == 0){
        countLearnWords();
        return;
    }
    
    //1. 해당 알파벳이 이미 선택되어 있을 경우, skip (true일 경우)
    if(alphaCheck[alphaIdx]){
        
        chooseRecursive(least, alphaIdx + 1);
        return;
    }
    
    //2. 해당 알파벳이 선택되지 않았을 경우,
    //해당 알파벳 선택하고 경우의 수 탐색
    alphaCheck[alphaIdx] = true;
    chooseRecursive(least -1, alphaIdx + 1);
    
    //해당 알파벳 선택하지 않고 경우의 수 탐색
    alphaCheck[alphaIdx] = false;
    chooseRecursive(least, alphaIdx + 1);
    
}

int main(){
    
    //N : 단어 개수, K : 배울 수 있는 글자 수
    cin >> N >> K;
    
    //단어들의 입력
    for(int i = 0; i < N; i++){
        cin >> words[i];
    }
    
    //anti ~ tica에서 atinc 알파벳 나머지 확인
    if( K < 5) { cout << 0 << endl; return 0; }
    
    //a c i n t 알파벳 방문 check
    alphaCheck[0] = true; alphaCheck[2] = true; alphaCheck[8] =true; alphaCheck[13] = true; alphaCheck[19] = true;
    
    
    //골라야 할 알파벳 최댓값
    
    //재귀 + 백트래킹
    chooseRecursive(K-5, 1);
    
    cout << learnMax << endl;

    return 0;
}

 

⏱ 결과

 

[느낀점]

골드 이상의 문제는 확실히 멍때리고 그냥 풀 문제가 아니고

분할정복 개념으로 해결해야하는 조건대로 함수를 만드는게 속편한 듯 하다...

 

골드 문제 하나 푸는 데 시간이 많이 걸린다. 연습이 많이 필요하다.