백준 2922 즐거운 단어

49.01m

나의 답

import sys
input = sys.stdin.readline

vow = ['A', 'E', 'I', 'O', 'U']
cons = ['B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z']
letters = input().rstrip()
length = len(letters)
res = 0

def is_possible(s):
    if 'L' not in s: return False
    for i in range(length - 2):
        if (s[i] in vow) and (s[i + 1] in vow) and (s[i + 2] in vow):
            return False
        if (s[i] in cons) and (s[i + 1] in cons) and (s[i + 2] in cons):
            return False
    return True

def bt(s, end, used):
    global res
    if '_' not in s:
        if is_possible(s):
            res += used
        return
    for i in range(end, length):
        if s[i] == '_':
            s = s[:i] + 'A' + s[i + 1:] # 모음 사용하는 경우
            bt(s, i + 1, used * 5)
            s = s[:i] + 'B' + s[i + 1:]  # 자음 사용하는 경우
            bt(s, i + 1, used * 20)
            s = s[:i] + 'L' + s[i + 1:]  # L 사용하는 경우
            bt(s, i + 1, used)
            return

bt(letters, 0, 1)
print(res)

이게 자꾸 DP이런걸 풀다보니까 문제를 봐도 의심하는데에 시간이 너무 많이 든다... 뭔가 내가 멍청하게 생각하는 것 같고..............
결국 검색으로 아이디어를 얻어서 풀긴했지만, 이 아이디어도 역시 처음에 문제보면서 고민하다가 '이렇게 풀면 되지 않나..? 근데 너무 빡구현느낌인데' 했던 솔루션이었다.

그래서 결론은 일단 풀어보고 말하자...