알고리즘/BOJ

백준 1062번 가르침

꾸준함. 2018. 10. 28. 01:37

문제 링크입니다: https://www.acmicpc.net/problem/1062


문제를 잘 못 파악해서 정말 많이 고민했던 문제였습니다.

처음에는 각각의 단어들을 개별적으로 봐서 익힐 수 있는 단어들의 수를 세는 줄 알았지만 문제의 의도는 K개의 알파벳을 배웠을 때 동시에 배울 수 있는 단어들의 수의 최댓값을 구하는 것이였습니다.


알고리즘은 아래와 같습니다.

1. 우선, anta와 tica는 무조건 포함됩니다. 따라서, 'a', 'c', 'i', 'n', 't'는 무조건 포함되므로 K가 5 미만이라면 절대 단어를 배울 수 없습니다.

2. 접두사로 anta, 접미사로 tica가 무조건 포함되므로 단어를 입력받을 때, 접두사와 접미사를 제거해줍니다.

3. 재귀를 통해서 문제를 풀어야하는데 우선 'a', 'c', 'i', 'n', 't'는 포함되어있다고 visited 배열에 표시를 해줍니다.

4. 매개변수로 배웠다고 표시해줄 알파벳과 익힌 알파벳의 수를 전달합니다.

5. 익힌 알파벳의 수가 K - 5가 되면 더 이상 익힐 수 없으므로 익힌 알파벳들로 배울 수 있는 단어들의 수를 셉니다. 그리고 최댓값을 최신화시킵니다.

6. 아직 알파벳을 익힐 수 있으면 브루트포스를 통해 알파벳 하나하나를 배웠다고 가정하고 재귀를 호출한 뒤 다시 배우지 않았다고 표시합니다.


#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int MAX = 50;

 

int N, K, result;

string word[MAX];

bool visited[26];

 

void howMany(int alpha, int cnt)

{

        //K개를 다 배운 경우

        if (cnt == K)

        {

                 int temp = 0;

                 for (int i = 0; i < N; i++)

                 {

                         bool flag = true;

                         //익히지 않은 알파벳이 있는 경우 배울 수 없는 단어

                         for(int j=0; j<word[i].length(); j++)

                                 if (!visited[word[i][j] - 'a'])

                                 {

                                          flag = false;

                                          break;

                                 }

 

                         if (flag)

                                 temp++;

                 }

                 result = max(result, temp);

                 return;

        }

 

        //아직 K개를 배우지 않은 경우: 브루트포스

        for (int c = alpha; c < 26; c++)

        {

                 if (!visited[c])

                 {

                         visited[c] = true;

                         howMany(c, cnt + 1);

                         visited[c] = false;

                 }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> K;

 

        //ANTA, TICA 무조건 포함

        if (K < 5)

        {

                 cout << 0 << "\n";

                 return 0;

        }

        //전부 익힐 수 있다

        else if (K == 26)

        {

                 cout << N << "\n";

                 return 0;

        }

 

        K -= 5;

        for (int i = 0; i < N; i++)

        {

                 cin >> word[i];

 

                 //anta

                 word[i] = word[i].substr(4, word[i].length());

                 //tica

                 for (int j = 0; j < 4; j++)

                         word[i].pop_back();

        }

 

        //a, c, i, n, t 무조건 포함

        visited['a' - 'a'] = true;

        visited['c' - 'a'] = true;

        visited['i' - 'a'] = true;

        visited['n' - 'a'] = true;

        visited['t' - 'a'] = true;

 

        howMany(0, 0);

        cout << result << "\n";

        return 0;

}


개발환경:Visual Studio 2017


지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형