3407번

3407번 - 맹세

이 문제 거의 이틀을 잡고 있었다... 재귀로 풀다가 시간초과.. 그래서 다시 고치면서 풀었더니 메모리 초과로 계속 골머리를 앓았다.

그래서 백준 슬랙을 통해서 갓님들의 피드백을 구했고, 어떤 갓님께서 직접 전화 통화로 설명해주셨다.

사실 생각보다 굉장히 심플했다, 내가 아주 복잡하게 파고들다 보니 그 속에 갇혔던 것 같다.

결국 마지막에 복기해보니, 나는 중간에 check를 해주는 처리를 해주지 않았다는 것을 깨달았다.

문자를 만들어갈때, 만약 map 을 통해 중복되는 문자를 체크하면 어땠을까 싶다.

즉 어떻게 해서든 한 단어를 만들어냈다면, 그 과정은 중요하지 않기 때문이다. 그 다음만을 생각하면 된다.

나는 계속 단어를 처음부터 만들어내는 방식으로 문제를 풀었고, 그러다보니 체크하는 과정을 떠올리지 못했다. 그런데 숫자로 바꿔서

문제를 풀다보니, 총 단어 길이는 50000 이므로 체크하는 배열을 만들어서 체크하면 엄청 빨라질 수 있었다.

로직은 BFS를 통해서 단어를 만들면서, 이미 만든 단어는 다시 큐에 들어가지 않도록 하면 된다.

<정답 코드>

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
using namespace std;
 
const int MAX = 114;
bool check[50001];
string v[MAX] = { "h", "b", "c", "n", "o", "f", "p", "s", "k", "v", "y", "i","w", "u","ba", "ca" , 
"ga", "la", "na", "pa", "ra", "ta", "db", "nb", "pb", "rb", "sb", "tb", "yb", "ac",
"sc", "tc", "cd", "gd", "md", "nd", "pd", "be", "ce", "fe", "ge", "he", "ne", "re", "se", "te",
"xe", "cf", "hf", "rf", "ag", "hg", "mg", "rg", "sg", "bh", "rh", "th", "bi", "li", "ni", "si",
"ti", "bk", "al", "cl", "fl", "tl", "am", "cm", "fm", "pm", "sm", "tm", "cn", "in", "mn", "rn",
"sn", "zn", "co", "ho", "mo", "no", "po", "np", "ar", "br", "cr", "er", "fr", "ir", "kr", "lr",
"pr", "sr", "zr", "as", "cs", "ds", "es", "hs", "os", "at", "mt", "pt", "au", "cu", "eu", "lu",
"pu", "ru", "lv", "dy" };
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        memset(check, false, sizeof(check));
        string s;
        bool chk = false;
        cin >> s;
 
        int end = s.size();
        priority_queue<int> q;
        q.push(0);
        check[0] = true;
 
        while (!q.empty())
        {
            int pos = q.top();
            q.pop();
 
            if (pos == end)
            {
                chk = true;
                break;
            }
 
            for (int i = 0; i < MAX; i++)
            {
                if (v[i][0] == s[pos] && v[i].size()==1 && !check[pos+1])
                {
                    check[pos + 1] = true;
                    q.push(pos + 1);
                }
 
                if (v[i][0] == s[pos] && v[i][1] == s[pos+1] && v[i].size()==2 && !check[pos+2])
                {
                    check[pos + 2] = true;
                    q.push(pos + 2);
                }
            }
 
        }
    
    
 
        if (chk)
        {
            cout << "YES" << "\n";
        }
        else
        {
            cout << "NO" << "\n";
        }
 
    }
 
    return 0;
}