1062

백준 1062번

Link: 1062번: 가르침

---

문제 설명

29일부터 풀기 시작해서 30일에서 31일 넘어가는 새벽에야 겨우 해결했던 문제.

내 답이 맞는것 같아 계속 고민하다 결국 답을 보고 해결했다.

답을 찾아보고서야 예전에 DFS를 통해 조합을 구하는 방법을 써서 문제를 풀때 어떤식으로 코드를 짰는지 떠오르더라.

정신승리를 좀 하자면, 시간초과가 났긴 했지만 어쨌든 답을 구할 수 있는 방법들을 최대한 생각해보고 여러 방법들을 비교해봤다는 점.

이러는 과정에서 시간초과를 수십번 본 것 같은데, 어떤 부분에서 시간초과가 일어나는지는 짚어냈다.

문제는 그 부분을 고치니 답이 틀렸다는 것.

이렇게 여러번 고민해봐도 도저히 안풀려서 답을 찾아보게 되었다.

답을 보고 나니 뭔가 매우 허무한 느낌이 들었다. 그동안 뭘 짜고 있었나 싶기도 하고.

답을 찾아내기 위해 삽질했던 시간들이 있었기 때문에 정답을 보고서도 이 부분은 나도 구현했는데 왜 틀렸을까 하는 생각이 들게 하였고 이 부분은 이래서 이렇게 짰구나 하는 생각도 들 수 있었던것 같다.

요며칠 단순한 BFS문제를 풀면서 이런식으로 DFS를 통해 조합을 구하고 백트래킹해야 풀리는 문제 푸는 연습을 해야겠다고 생각했는데, 이 문제가 전형적인 그런 문제였다.

시간 지나고 푸는 방법 까먹을때쯤 한번 더 풀어봐야겠다.

---

삽질했던 코드

#include <iostream>
#include <vector>

using namespace std;

int result = 0;
int N, K;
int candidates[26] = {0, };
int words[50][26] = {0, };

int max(int a, int b){
    return a > b ? a : b;
}

void searchTeach(int count, int index, int toTeach[26], int limit){
    int tempResult = 0;

    int temp[26];
    for(int i=0; i<26; i++){
        temp[i] = toTeach[i];
    }

    if(candidates[index] == 1){
        temp[index] = 1;
    }

    if(count == limit){
        for(int i=0; i<N; i++){
            bool invalid = false;

            for(int j=0; j<26; j++){
                if(toTeach[j] - words[i][j] < 0){
                    invalid = true;
                    break;
                }
            }

            if(!invalid){
                tempResult++;
            }
        }

        result = max(result, tempResult);
        return;
    }

    int next = 0;
    for(int i=index+1; i<26; i++){
        if(candidates[i] == 1){
            next = i;
            break;
        }
    }

    searchTeach(count+1, next, temp, limit);
    searchTeach(count+1, next, toTeach, limit);
}

void toTeach(){
    for(int i=0; i<N; i++){
        for(int j=0; j<26; j++){
            if(candidates[j] != 1){
                candidates[j] = words[i][j];
            }
        }
    }
}

int main(){
    string word;

    cin >> N >> K;

    for(int i=0; i<N; i++){
        cin >> word;

        if(K >= 5){
            string temp = word.substr(4, word.length()-8);
            for(int j=0; j<temp.length(); j++){
                int current = temp[j] - 'a';
                if(current != 0 && current != 2 && current != 8 && current != 13 && current != 19){
                    words[i][current] = 1;
                }
            }
        }
    }

    if(K < 5){
        result = 0;
    }
    else{
        toTeach();

        int input[26] = {0, };

        for(int i=0; i<26; i++){
            if(candidates[i] == 1){
                searchTeach(0, i, input, K-5);
                candidates[i]--;
            }
        }

        if(K == 5){
            searchTeach(0, 0, input, K-5);
        }
    }

    cout << result << '\n';

    return 0;
}

---

정답 코드

//
// Created by Keith_Lee on 30/01/2019.
//

#include <iostream>
#include <vector>

using namespace std;

int result = 0;
int N, K;

string words[50];
bool visit[26];

int max(int a, int b){
    return a > b ? a : b;
}

void searchTeach(int index, int count){
    if(count == K-5){
        int tempResult = 0;

        for(int i=0; i<N; i++){
            bool invalid = false;

            for(int j=0; j<words[i].length(); j++){
                if(!visit[words[i][j] - 'a']){
                    invalid = true;
                    break;
                }

            }

            if(!invalid){
                tempResult++;
            }
        }

        result = max(result, tempResult);
        return;
    }

    for(int i=index; i<26; i++){
        if(!visit[i]){
            visit[i] = true;
            searchTeach(i, count+1);
            visit[i] = false;
        }
    }

}

int main(){
    cin >> N >> K;

    for(int i=0; i<N; i++){
        cin >> words[i];

        words[i] = words[i].substr(4, words[i].length()-8);
    }

    if(K < 5){
        result = 0;
    }
    else if(K == 26){
        result = N;
    }
    else{
        visit['a' - 'a'] = true;
        visit['n' - 'a'] = true;
        visit['t' - 'a'] = true;
        visit['c' - 'a'] = true;
        visit['i' - 'a'] = true;

        searchTeach(0, 0);
    }

    cout << result << '\n';

    return 0;
}

---