백준 2922 즐거운 단어

오늘의 문제: 2922번: 즐거운 단어 (acmicpc.net)

2922번: 즐거운 단어

도무지 풀리지 않아서 일주일 가까이를 붙잡고 있었던 문제.

오랜만에 코딩 문제를 풀어서 그런가 정말 풀리지가 않았다...

결국 구글링 찬스를 써서 약간의 힌트를 봤더니 해결되었다;

 

조건에서 (1) 자음이나 (2) 모음이 연속으로 세 개가 나오면 안 되고 (3) L을 반드시 포함해야 한다고 했으므로

문자를 자음, 모음, L 세 개로 나누어서 단순화할 수 있겠다.

 

다른 글에서도 찾을 수 있지만, 즐거운 단어는 빈칸이 10개이다.

만약 자음(C: Consonant), 모음(V: Vowel), L로 나눈다 치면, C, V, L로 10칸을 채우는 경우는 브루트 포스를 하더라도 3^10=59049이므로 충분히 할 수 있는 경우가 된다.

 

그리고 여기서 정답은 64비트 정수 범위이므로, long long으로 정답을 처리하면 된다.

 

그런데 여기서 문제점은 printf를 사용할 때 생기게 되는데, 아무 생각 없이 포맷을 %d나 %ld를 사용하면 long long을 담아내지 못해 실패하게 된다.

 

그러니까 %lld를 사용해서 표현해야 제대로 문제를 풀 수 있다.

 

 

 

 

내가 해결한 방법은 모든 문자를 C(L을 제외한 자음), V(모음), L, _(빈칸)로 바꾸어 푸는 것이었다.

모든 문자를 채우고 나서(word[index] == '\0')는 모든 문자를 쭉 돌면서 맞는지 아닌지를 확인한다.

만약 모든 조건을 만족한다면 1을 반환하는 식으로 해서, 재귀로 돌며 해결하였다.

 

// 3. 백준 2922 즐거운 단어(https://www.acmicpc.net/problem/2922)
#include <cstdio>
#include <cstring>
 
char word[101];
long long makeword(int index)
{
    while(true)
    {
        if (word[index] == '\0')
        {
            int c = 0, v = 0;
            bool l = false;
            for (int i = 0; i < index; i++)
            {
                if (word[i] == 'C' || word[i] == 'L')
                {
                    c++;
                    v = 0;
                    if (word[i] == 'L') l = true;
                }
                else if (word[i] == 'V')
                {
                    v++;
                    c = 0;
                }
                
                if (c >= 3 || v >= 3)
                    return 0LL;
            }
            if (l == true) { return 1LL;}
            else return 0LL;
        }
        if (word[index] == '_')
        {
            long long result = 0LL;
            word[index] = 'C'; result += 20LL * makeword(index + 1);
            word[index] = 'V'; result += 5LL * makeword(index + 1);
            word[index] = 'L'; result += makeword(index + 1);
            word[index] = '_';
            return result;
        }
        index++;
    }
}
 
int main()
{
    scanf("%s", word);
    int len = strlen(word);
    for (int i = 0; i < len; i++)
    {
        char c = word[i];
        if (c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U')
            word[i] = 'V';
        else if (c != '_' && c != 'L')
            word[i] = 'C';
    }
    printf("%lld\n", makeword(0));
}

 

알고 보면 정말 단순한 문제라서 더 허무하다.